Finding Molecules with Specific Properties: Simulated Annealing vs. Evolution

This paper compares simulated annealing and evolutionary algorithms, both utilizing SMILES string representations, and finds them to be equally effective for discovering molecules with large molecular average hyperpolarizabilities for nonlinear optical applications.

The Gist

Imagine you are a master chef trying to invent the ultimate dessert. You know exactly what you want: a cake that is not just delicious, but has a magical "spark" that makes it glow in the dark (in the scientific world, this "spark" is called hyperpolarizability, a property that makes materials interact with light in special ways, useful for things like lasers and fiber optics).

The problem? There are billions of possible recipes (molecules) you could make. You can't taste them all one by one; it would take forever. So, you need a smart assistant to help you search through the recipe book and find the best one.

This paper compares two different "smart assistants" to see which one is better at finding that perfect glowing dessert: The Evolutionary Chef and The Simulated Annealing Chef.

The Two Assistants

1. The Evolutionary Chef (Nature's Way)

Think of this assistant as a biological breeder. It starts with a small group of 10 "parent" recipes.

• Mixing and Matching: It takes two parents and "couples" them to create "children" recipes. It might take the frosting from one and the crust from another. This is called crossover.
• Random Tweaks: Sometimes, it randomly changes an ingredient (like swapping sugar for honey) or adds a new spice. This is called mutation.
• Survival of the Fittest: It makes 20 new recipes. Then, it tastes them all. The ones that glow the brightest get to be parents for the next round. The dull ones are thrown in the trash.
• The Result: Over 100 rounds (generations), this method is like a fast-forwarded version of evolution. It found a recipe that improved the "glow" by 63%.

2. The Simulated Annealing Chef (The Metalworker's Way)

Think of this assistant as a blacksmith trying to shape a piece of metal.

• The Process: The blacksmith starts with one specific recipe. He makes a tiny change to it (like adding a pinch of salt).
• The Risk: If the new recipe is better, he keeps it. But here's the clever part: if the new recipe is worse, he might still keep it anyway!
• Why? Imagine you are in a valley and want to get to the highest mountain peak. If you only ever move uphill, you might get stuck on a small hill that looks like a peak but isn't. By occasionally accepting a "worse" step, the blacksmith can wander out of small valleys to find the real highest mountain.
• The Result: This method is very careful and methodical. In 100 steps, it improved the "glow" by 13%.

The Showdown: Who Wins?

The authors ran a race between these two chefs to see who could find the best molecule faster.

• The Evolutionary Chef is like a sprint team. It tries many different combinations at once. It found a much better molecule overall (63% improvement). However, it requires a lot of "tasting" (computer calculations) to do this.
• The Simulated Annealing Chef is like a solo explorer. It takes fewer steps to get started and is very good at exploring the immediate area. In the very beginning (the first few dozen steps), it actually found good molecules slightly faster than the Evolutionary Chef. But it gets stuck in a "local maximum" (a good, but not great, solution) sooner.

The Big Takeaway

The paper concludes that both methods are useful, but they have different strengths:

1. If you have a lot of time and computing power: Use the Evolutionary Algorithm. It's like sending out a whole army of scouts; eventually, they will find the absolute best treasure.
2. If you need a quick, decent answer: Use Simulated Annealing. It's like sending one very smart scout who is willing to take risks to avoid getting stuck.

The "Secret Sauce" (SMILES):
Both chefs used a special language called SMILES to write down their recipes. Instead of drawing complex 3D pictures of molecules, they used simple text strings (like C-C-N-O). This made it easy for the computer to chop, swap, and rearrange the ingredients just like a chef rearranging letters in a word.

The Final Dish

The best molecule found by the Evolutionary Chef (shown in Figure 3 of the paper) is a complex organic structure that glows incredibly bright. While the scientists need to double-check the math with more powerful computers, this experiment proves that computer algorithms can act like creative chemists, inventing new materials that humans might never have thought to try.

In short: Nature (Evolution) is great at finding the best solution over time, while careful trial-and-error (Annealing) is great at finding a good solution quickly without getting stuck. Both are essential tools for the future of material science.

Technical Summary

1. Problem Statement

The core challenge addressed is the inverse design problem in chemistry: identifying a molecular structure that possesses a specific set of desired properties, rather than calculating properties from a known structure.

• Target Property: The study focuses on maximizing molecular average hyperpolarizability ($\beta$), a critical metric for Nonlinear Optical (NLO) materials. High $\beta$ values allow molecules to modify light frequency, phase, and polarization.
• Complexity: The solution space is vast, and the variables (atomic arrangements) are discrete rather than continuous, making traditional gradient-based optimization methods unsuitable.
• Representation: Molecules are represented as SMILES (Simplified Molecular Input Line Entry Specification) strings, a standard ASCII-based notation for chemical structures.

2. Methodology

The authors compared two distinct optimization algorithms: an Evolutionary Algorithm (EA) and Simulated Annealing (SA). Both methods utilized the same fitness function and molecular representation.

A. Common Components

• Fitness Function: The hyperpolarizability ($\beta$) calculated using MOPAC (an open-source semi-empirical quantum chemistry program) with the PM6 force field.
• Search Space: Molecules composed exclusively of Carbon (C), Oxygen (O), and Hydrogen (H).
• Initial Population: Ten promising NLO candidate molecules identified in previous literature (Table 1).
• Mutation Operators: Both algorithms utilized seven specific mutation operators to manipulate SMILES strings:
  1. Changing bond types (single/double/triple).
  2. Adding atoms with random bonds.
  3. Adding atoms as new branches.
  4. Deleting atoms and bonds.
  5. Changing atom types.
  6. Connecting two atoms to form a ring.
  7. Deleting existing rings.

B. Evolutionary Algorithm (EA)

• Population: 10 parents and 20 children per generation.
• Operators:
  • Mutation: Applied based on a random number threshold.
  • Crossover: A "cut and splice" method where two parent strings are broken at random bond points and recombined.
• Selection Strategy: A tiered selection process to maintain diversity and avoid local minima:
  • Top 40% of the highest fitness group survive.
  • 30% from the second group, 20% from the third, and 10% from the fourth.
• Duration: 100 generations.
• Variation: Tested with different mutation/crossover ratios (10/90, 30/70, 50/50, 70/30).

C. Simulated Annealing (SA)

• Mechanism: A stochastic optimization method that accepts worse solutions with a probability determined by a "temperature" parameter ($T$) to escape local minima.
• Parameters:
  • Fixed temperature $T = 20$ (chosen for good convergence in prior studies).
  • Acceptance function based on the Metropolis criterion: $A = \min(R, \exp([f(x_{new}) - f(x_{initial})]/T))$.
• Duration: 100 steps.
• Process: Starting from a single initial molecule, the algorithm generates new SMILES strings via mutation. If the new $\beta$ is higher, it is accepted; if lower, it is accepted probabilistically.

3. Key Results

Performance Comparison

• Evolutionary Algorithm:
  • The 10% mutation / 90% crossover ratio yielded the fastest convergence.
  • Over 100 generations, the average $\beta$ increased by 63% (from ~4,137 to ~261,334 atomic units).
  • High Variance: The 10/90 configuration showed a large standard deviation because different random seeds produced vastly different final values (ranging from ~13k to ~649k).
  • Best Result: One run produced a molecule with $\beta = 649,417$ atomic units.
• Simulated Annealing:
  • Over 100 steps, the average $\beta$ increased by 13% (from ~3,389 to ~44,962 atomic units).
  • Low Variance: Results were more consistent across different random seeds, with a smaller standard deviation.
• Efficiency (Function Evaluations):
  • When plotting $\beta$ against the number of function evaluations (N), SA performed slightly better than the EA in the early stages (0–640 evaluations).
  • However, the EA eventually outperformed SA significantly as the number of evaluations increased, largely due to the power of the crossover operator in exploring the search space.
  • Note: SA required ~6 evaluations per step (averaging valid mutations), while EA required exactly 20 evaluations per generation.

4. Key Contributions

1. Algorithmic Comparison: Provides a direct empirical comparison between Simulated Annealing and Evolutionary Algorithms for discrete molecular optimization using SMILES strings.
2. Validation of Crossover: Demonstrates that crossover operators are crucial for the rapid convergence of evolutionary algorithms in cheminformatics, allowing the algorithm to combine beneficial structural motifs effectively.
3. Feasibility of Semi-Empirical Methods: Shows that semi-empirical methods (PM6/MOPAC) are viable for high-throughput screening in optimization loops, despite their lower accuracy compared to ab initio methods, due to computational speed.
4. Discovery of High-Performance Candidates: Successfully identified novel molecular structures with significantly enhanced hyperpolarizabilities compared to the initial starting set.

5. Significance and Future Work

• Material Science Impact: The study confirms that global optimization algorithms can effectively navigate the vast chemical space to discover NLO materials, a task difficult for manual trial-and-error.
• Robustness: Both algorithms proved robust for discrete variable problems, suggesting they can be applied to other molecular design challenges (e.g., drug discovery, battery materials).
• Future Directions:
  • Validation: The authors plan to verify the highest $\beta$ value ($649,417$) using more accurate, computationally expensive quantum chemical methods.
  • Multi-Objective Optimization: Future work will aim to simultaneously optimize other physical requirements for NLO materials, such as thermal stability and optical transparency, rather than maximizing $\beta$ in isolation.
  • Algorithm Refinement: Investigating advanced variations of the EA and SA to further improve convergence speed and solution quality.