> ## Content Index
> Fetch the complete content index at: https://starikov.co/llms.txt
> Use this file to discover other available public pages before exploring further.

# The Reusability Of Evolutionary Algorithms
- URL: https://starikov.co/ea-reuse/
- Published: 2018-10-01T18:11:00.000Z
- Updated: 2026-06-09T23:01:26.000Z
- Description: 3-SAT Solving With EAs
- Author: Illya Starikov
- Tags: AI, Code, Computer Science, #u-color-bg-tag-accent, #u-color-text-dark

Let's propose an Evolutionary Algorithm experiment; say we already have a framework in place (like the [Secret Message](https://starikov.co/ea-intro/) framework we previously implemented). How difficult would it be to completely switch problem instances?

First, we need another problem instance. Our previous problem instance was pretty straightforward: it had one local optimum. Let's take on a problem with *many* local optima, such as the [3-SAT problem](https://en.wikipedia.org/wiki/Boolean%5Fsatisfiability%5Fproblem?ref=starikov.co#3-satisfiability).

The premise of 3-SAT is simple. From a global pool of variables (\\(x\_1\\), \\(x\_2\\), \\(\\ldots\\), \\(x\_n\\)), we have a basic clause of three variables or-ed together (signified by \\(\\vee\\)):

$$x\_p \\vee x\_q \\vee x\_r$$

Then, and (signified by a \\(\\wedge\\)) several clauses together:

$$\\left(x\_p \\vee x\_q \\vee x\_r\\right) \\wedge \\left(x\_s \\vee x\_t \\vee x\_u\\right) \\wedge \\ldots \\wedge \\left(x\_v \\vee x\_w \\vee x\_y\\right)$$

The only stipulation is that any variable can be negated (signified by a \\(\\neg\\)). So, supposing we want to negate \\(x\_p\\); \\(x\_s\\) and \\(x\_u\\); and \\(x\_v\\), \\(x\_w\\), and \\(x\_y\\); we can do the following:

$$\\left(\\neg x\_p \\vee x\_q \\vee x\_r\\right) \\wedge \\left(\\neg x\_s \\vee x\_t \\vee \\neg x\_u\\right) \\wedge \\ldots \\wedge \\left(\\neg x\_v \\vee \\neg x\_w \\vee \\neg x\_y\\right)$$

Now, we simply have to assign all the variables such that all the clauses will evaluate to true. It may sound simple, but it belongs to the [hardest classes of problems in computer science](https://en.wikipedia.org/wiki/NP-completeness?ref=starikov.co#NP-complete%5Fproblems). There is no guaranteed algorithm to produce the right answer at this time.

For a more visual approach, please reference the figure below. The goal is to make every inner node green, by having at least one connected outer node be green. Note the green nodes have to account for negation as well.

![](https://starikov.co/content/images/2025/06/sat-easy-solution.png)

This sounds like a good problem candidate for an Evolutionary Algorithms.

## The SAT Problem

We can skip over the problem specific parts to worry more about the Evolutionary Algorithm aspect. Suppose we already have a well-defined `SAT` class that takes care of SAT-specific properties and methods, like so:

```python
class SAT:
    def __init__(self, filename):
        """Create a SAT object that is read in from a CNF file."""
        ...

    @property
    def variables(self):
        """Get *all* the variables."""
        ...

    @property
    def total_clauses(self):
        """Get the total number of clauses."""
        ...

    @property
    def clauses_satisfied(self):
        """Get the number of satisfied clauses."""
        ...

    def __getitem__(self, key):
        """Get a particular variable (key)"""
        ...

    def __setitem__(self, key, value):
        """Set a variable (key) to value (True/False)"""
        ...

```

From this, we can create a new genotype for our `Individual`.

## The New Genotype

The genotype structure was very similar to what we had before:

- The genotype is the `SAT` problem we defined above.
- Fitness is defined by a percentage of the total satisfied clauses.
- Mutation is uniform, choose a percentage \\(p\\) of alleles and flip their value.
- Recombination is uniform, randomly assemble values from both parents.

Looking at the refactoring, not much has changed.

![](https://starikov.co/content/images/2025/06/sat-secret-message-diff.png)

## The New EA Framework

Now that we have updated our Individual, the next thing to update would be the Evolutionary Algorithm framework, including:

- The Population
- The EA Itself

*Except, we don't have to*.

That's the beauty of Evolutionary Algorithms, they are incredibly adaptable. By swapping out the Individual, the rest of the evolutionary algorithm should still work.

For our SAT problem, there were some parameters updated, to make the algorithm more efficient:

- The mutation rate has been reduced to 5%
- The tournament size has been reduced to 15 individuals (out of \\(\\lambda = 100\\)).

## The Result

So, let's try our Evolutionary Algorithm. Taking a SAT instance with 75 variables and 150 clauses, this makes the search space

$$2^{75} \\approx 3.77 \\times 10^{22}$$

Great, so roughly 1,000 times the grains of sand on Earth, easy. So, can our EA do it?

After roughly 100 iterations, *yes*. See the visualization below.

![](https://starikov.co/content/images/2025/06/sat-result.png)

Marvelous, our EA managed to find a solution after only 100 iterations in a giant search space. And all we had to do was swap out one class.