Search code examples
algorithmcomparegenetic-algorithmparticle-swarm

Compare the structure of Genetic Algorithm (GA) with the structure of Particles swarm Optimization (PSO)

When we compare the structure of Genetic Algorithm (GA) with the structure of Particles swarm Optimization (PSO) is possible to say that:

  1. The Population in GA = the Swarm in PSO.

  2. The chromosome (potential solution) in GA = the Particle (potential solution) in PSO.

  3. The genes of a chromosome in GA = the coordinates of a particle in PSO.

Solution

  • As you must be knowing that both GA(Genetic Algorithm) and PSO(Particle Swarm Optimization) come under the Evolutionary Computation. These two evolutionary heuristics are population-based search methods.

    As if, we consider the case of original GA (i'm not even talking about slightly modified GA, here). It was inspired by the principles of genetics and evolution, and it mimics the reproduction behavior observed in biological population or environment. It follows the principle of "survival of fittest" to select and generate offsprings which are adapted to the environment or constraints. Whereas, if we talk about PSO. It was inspired by the behavior observed in the school of fish and swarm of birds. How do they react or behave to external stimuli (to achieve maxima or minima in the fitness function) using their cognitive and collective power?

    PSO is considered as improvement over GA, because it takes less time to compute the desired results. Whereas, GA is still being used by many people and companies, because of ease of implementation and understanding.

    Now, let's discuss about your questions:

    1. The Population in GA = the Swarm in PSO ?

    I think the answer is yes, but not always. Because there are some cases where we can't represent the population in terms of PSO directly, but we can represent it in the case of GA. For example - If we consider discrete vector represent, then we can easily go for GA but we'll have to make few modification before feeding the vector into the PSO algorithm.

    1. The chromosome (potential solution) in GA = the Particle (potential solution) in PSO?

    Perhaps, you can be right. But let me remind you why we use EC techniques? Since, the number of possible solutions to the problem (which is solved by using EC techniques) generally has very large number of state spaces. And, we are only considering the fraction of it as our output or result. Thus, even if we have reached to the required benchmark, we can't be sure that the results will match up.

    1. The genes of a chromosome in GA = the coordinates of a particle in PSO?

    As, we all know that GA is inherently designed to evaluate the discrete vector representation, where as, PSO performs best with unconstrained problems with continuous variables. And since, the original PSO was not very immune to local maxima or minima. Therefore, it may sometimes show premature convergence under the constraints. which is rarely seen in GA (thanks to mutation). So, I'd say No. The genes of the chromosomes in GA are not always the coordinates of the particles in PSO.

    EDIT:

    Could you please give me a simple example for this: "... we'll have to make few modification before feeding the vector into the PSO algorithm."

    Since i already told you that GA is inherently designed for discrete evaluation whereas PSO works better in case of continuous variables. Let us consider a case. Where we are given a family of strings of 0 and 1. and we are to satisfy the given fitness function f(x) to terminate the loop. As we all know that 0 and 1 are two discrete numbers. Thus on apply crossover or mutation (in case of GA) we will get the discrete output. After that we will feed this output into the fitness function to check its strength. If it survives the f(x) then we will push that output to the next generation.

    But in case of PSO, we generally consider position vector or a string of '0' and '1' of this case, and velocity vector or probability of changing the number to its opposite number (means probability of changing 0 to 1 and vice versa). Now, suppose the probability of changing the value 0 into 1 is 0.6 and 1 into 0 is 0.3. Then on apply the probability distribution we will get a transition state which either holds 0 or 1 with some degree of probability. In other words, the upcoming state will contain the values between 0 and 1 included, which is not correct itself. And, since we were only expecting discrete numbers. Thus, we'll have to put some benchmark like- below 0.5 will be 0(zero) and above 0.5 will be 1(one).And, now this benchmarked or modified output will be used as an input for the next generation.