“This is the 12th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

Tomorrow will be New Year’s Eve, the New Year, so tomorrow will not update the blog. As for this blog post, I stumbled on site B and found a video about genetic algorithms by UP (don’t worry about Python). Then I looked at the code he wrote and compared my code and found that there were many points that could be optimized. Also do a small record, elaborate the implementation steps of genetic algorithm, and some written in python can directly open to hang (I previously written code is implemented using the list directly in many parts of the code are made wheels, dubious ~), then the code is that UP to the main code, shows that optimization.

So the first thing we need to know is what is genetic algorithm

Genetic algorithm (ga)

Genetic algorithms are essentially computer simulations of our species’ evolution. In fact, a more popular term is screening, which is the same as our grandpa Yuan Longping planting rice. Some of them are good and some of them are not, so I select the ones that are good, and then I let them reproduce, and then I select them, and then I get high yield rice. In fact, just like our society, if you don’t work hard, you don’t have a girlfriend, you can’t keep your genes, and then the rest of the people are the genes of those excellent people and the rich second generation, this is the reality. So have to study hard, day day up! So back to the theme, our genetic algorithm is simulating this process, simulating natural selection.

So there are chunks in our algorithm

breeding

First, our species needs to reproduce. So that we can keep producing good basis, so for our algorithm, let’s say we need to find

Y = np.sin(10 * x) * x + np.cos(2 * x) * x

The maximum value of phi (in a range) then our individual is a set of (X1) solutions. The good ones will be retained, the bad ones will be passed, and the selection criteria will be our function Y. So the question is how do you simulate this? We all know that when we reproduce, we retain our genetic information through DNA, and in this process, the parents’ DNA interacts with each other, and in this process, mutations occur, so that the best bits of both parents are preserved, and the mutations that occur are likely to produce better offspring. So next we need to simulate our DNA, crossing and mutating.

cross

This crossover process is actually very similar to our biology, and of course we have numbers in our computers that we can convert into binary as our DNA

There are a lot of ways to cross over, so let’s take this one and cross over.

variation

So this is a little bit easier in our case where we just randomly pick a couple of places to change the values after the crossover. Of course, the probability of variation is very small, and it’s random, so be aware of that. And since the variation is random, it does not rule out creating individuals who are worse off than before.

choose

Finally, we select this individual according to certain rules, and then eliminate the original individual. So we’re using two things in our computer, we’re going to take the binary stuff, we’re going to convert it to our decimal stuff and we’re going to put it in our function, and we’re going to save it, and then we’re going to filter it every time.

The code

“Open hang API”

Before we start writing our code, we have to introduce a few apis that numpy’s API is literally open and shut, and it’s these apis that make the most difficult parts of writing fairly easy. It is also these apis that make it difficult for many people to read the code because it is not explained, even in the source code.

numpy.random.randint()

The API is not as easy to use as I said earlier. Its use is quite ingenious.

**low: int

The generated value must be greater than or equal to low. (If hign = None, the generated value must be in the range [0, low).) High: int (Optional) If this value is used, the generated value is in the range [low, high). Size: Int or tuple of ints(Optional) Specifies the size of a random number. For example, size = (m * n* k) specifies the size of a random number. Output: out: int or ndarray of INts returns a random number or array of random numbers **

Just write a low argument

Two low and height

Elements to replace

This actually has a lot to do with Numpy, which supports Boolean arithmetic.

So that’s it.So if we wanted to swap the elements of our two ARry arrays we could just do that and just pay attention to the dimensions here

Is that a direct element exchange, a DNA crossover.

np.random.choice

This is also the open hanging thing, and we said earlier that we’re going to filter which is select. So just using this function, we’re done.

First, the basic usage.

np.random.choice(5)Print a random number from [0, 5]
Copy the code
L = [1, 2, 3, 4, 5] # list list np. Random. Choice (L, 5) > > > array ([4, 3, 5, 3, 3))Copy the code
L = [1, 2, 3, 4, 5]#list np.random. Choice (L, 5, replace=True)#Copy the code

The weightAnd that’s where we get toSo it’s clear what to do next.

Of course, the purpose of our selection is to get rid of the bad individuals, so it is to choose the good individuals. See the specific code.

The code structure

Well, with all the nonsense, we can finally start coding. There are actually several pieces here, the ones in front of us.

The complete code

There’s a note in there that doesn’t explain it

import numpy as np
import matplotlib.pyplot as plt


Population_Size = 100
Iteration_Number = 200
Cross_Rate = 0.8
Mutation_Rate = 0.003
Dna_Size = 10
X_Range=[0.5]


def F(x) :
    Target function, function to be optimized :param x: :return: ""
    return np.sin(10 * x) * x + np.cos(2 * x) * x

def CrossOver(Parent,PopSpace) :
    "Cross DNA, we just choose one of the species to mate and have a baby :param parent: : Param PopSpace: :return:"
    if(np.random.rand()) < Cross_Rate:

        cross_place = np.random.randint(0.2, size=Dna_Size).astype(np.bool)
        cross_one = np.random.randint(0, Population_Size, size=1) # Choose a male/female mate
        Parent[cross_place] = PopSpace[cross_one,cross_place]

    return Parent

def Mutate(Child) :
    Variable :param Child: :return: ""
    for point in range(Dna_Size):
        if np.random.rand() < Mutation_Rate:
            Child[point] = 1 if Child[point] == 0 else 0
    return Child


def TranslateDNA(PopSpace) :
    Convert binary to decimal for easy calculation :param PopSpace: :return: ""
    return PopSpace.dot(2 ** np.arange(Dna_Size)[::-1) /float(2 ** Dna_Size - 1) * X_Range[1]

def Fitness(pred) :
    "" This is actually the conversion of the F(x) that we got, which is the probability of the selection, we need to deal with negative numbers, because the probability can't be negative pred this is a two-dimensional matrix :param pred: :return:" "

    return pred + 1e-3 - np.min(pred)

def Select(PopSpace,Fitness) :
    "Select: Param PopSpace: : Param Fitness: : Return:"
    "And the thing to notice here is that we first select our good ones by weight, so when we select here we allow duplicate elements and then we get rid of those duplicate elements, so that we can keep the good ones and get rid of the bad ones. If repetition is not allowed, you are not filtering.
    Better_Ones = np.random.choice(np.arange(Population_Size), size=Population_Size, replace=True,
                           p=Fitness / Fitness.sum())
    # np.unique(Better_Ones) # this is what I added at the end

    return PopSpace[Better_Ones]


if __name__ == '__main__':
    PopSpace = np.random.randint(2, size=(Population_Size, Dna_Size))  # initialize the PopSpace DNA

    plt.ion() 
    x = np.linspace(X_Range, 200)

    # plt.plot(x, F(x))
    plt.xticks([0.10])
    plt.yticks([0.10])

    for _ in range(Iteration_Number):
        F_values = F(TranslateDNA(PopSpace))  

        # something about plotting
        if 'sca' in globals():
            sca.remove()
        sca = plt.scatter(TranslateDNA(PopSpace), F_values, s=200, lw=0, c='red', alpha=0.5)
        plt.pause(0.05)

        # GA part (evolution)
        fitness = Fitness(F_values)
        print("Most fitted DNA: ", PopSpace[np.argmax(fitness)])
        PopSpace = Select(PopSpace, fitness)
        PopSpace_copy = PopSpace.copy()
        for parent in PopSpace:

            child = CrossOver(parent, PopSpace_copy)
            child = Mutate(child)

            parent[:] = child

    plt.ioff()
    plt.show()
Copy the code

conclusion

Advantages of genetic algorithm:

  1. Ability to search quickly and randomly with no concern for the problem area.
  2. The search starts from the group, has the potential parallelism, can carry out the simultaneous comparison of multiple individuals, robust.
  3. Search using evaluation function heuristic, the process is simple
  4. Using probabilistic mechanism for iteration, with randomness.
  5. It is extensible and easy to combine with other algorithms.

Disadvantages of genetic algorithm:

  1. The programming implementation of genetic algorithm is quite complicated. Firstly, the problem needs to be coded, and then the problem needs to be decoded after finding the optimal solution
  2. The realization of the other three operators also has many parameters, such as crossover rate and mutation rate, and the choice of these parameters seriously affects the quality of the solution, but at present the choice of these parameters mostly depends on experience.
  3. The feedback information of the network cannot be used in time, so the search speed of the algorithm is slow, and more training time is needed to obtain a more accurate solution.
  4. The algorithm has certain dependence on the selection of initial population and can be improved by combining some heuristic algorithms.
  5. The potential capability of parallel mechanism of algorithm has not been fully utilized, which is also a hot research direction of genetic algorithm.
In the current work, genetic algorithm (proposed in 1972) has not been able to solve the problem of large scale computation, it is easy to fall into "premature". Commonly used hybrid genetic algorithm, cooperative coevolution algorithm and so on to replace, these algorithms are GA derived algorithms.Copy the code

Genetic algorithm has good global search ability and can quickly search all the solutions in the solution space without falling into the trap of fast descent of local optimal solutions. And using its inherent parallelism, the distributed computation can be carried out conveniently and the solving speed can be accelerated. However, the local search ability of genetic algorithm is poor, which leads to the time consuming of simple genetic algorithm and the low search efficiency in the late evolution period. In practice, genetic algorithm is prone to premature convergence. It is always a difficult problem in genetic algorithm which selection method should not only keep the good individuals, but also maintain the diversity of the population.

In human language, first of all, in order to ensure global search, the convergence is slow (not so fast to find the point), in order to improve the speed, make the algorithm run faster, it is easy to run too fast (at a moment there are too many rich second generation genes are in the local optimal). This parameter is hard to set

For example,

You don’t note that the population is the same, there’s more variation possible to some extent. You annotate, the number goes down might go down. Of course 100 is not obvious. You can try, if you have 100 individuals it’s going to be different, but not by much, if you have 10,000 it’s going to be the same. And then there’s your mutation rate, your exchange rate.