Solving OneMax Problem Using Genetic Algorithm in Matlab

Hello everyone!

In this post, I am going to show you my Genetic Algorithm for solving One-max problem.

This Genetic Algorithm is coded in Matlab, and it is possible to customize, and modify this code with minimum change, to solve various optimization problems in your fields. No need to build this kind of Matlab code of Genetic Algorithm from scratch, because it’s very time-consuming. Updating, customizing, and/or modifying this Genetic Algorithm, to solve new optimization problems in your fields should be used.

Here is a description of One-Max problem:

It should be noted that, the complexity of One-Max problem depends on the size of the problem, which means that, the larger size of the problem, more difficult to find the optimal solution.

Based on my research, in terms of the number of journal articles, Genetic algorithm is the most popular stochastic optimization algorithm, in all 18 different research fields, as indicated in this Table. Do you believe that? For more details, please have a look at the reference attached.

Here is a general structure of a Genetic Algorithm:

Genetic Algorithm is a popular meta-heuristic, or stochastic optimization algorithm, based on the mechanisms of natural selection in Charles Darwin’s theory of natural evolution.

Genetic Algorithm was first introduced by Holland in 1975, and now it is still very popular in various research community.

Genetic algorithm starts with an initial set of random solutions, which is called, population. Each individual in the population is called a chromosome, representing a solution to the problem at hand. The chromosomes evolve through successive iterations, called generations. During each generation, the chromosomes are evaluated using some measures of fitness. To create the next generation, new chromosome, called, offspring, are formed by either, (a), merging two chromosomes from current generation using a crossover operator, or, (b), modifying a chromosome using a mutation operator. A new generation is formed by, (a), selecting, according to the fitness values, some of the parents and offspring, and, (b), rejecting others, so as to keep the population size constant. Fitter chromosomes have higher probabilities of being selected. After several generations, the algorithms converge to the best chromosome, which hopefully represents the optimal, or sub-optimal solution to the problem.

Chromosome representing a potential solution to One-Max problem is very simple; it is just a binary string. Here is one example with a size of 20.

Here is a main program of my Genetic Algorithm in Matlab:

Let’s see how it works:

The Matlab Code:

population.m

function Y = population(n,s)
% n = population size
% s= size of the MaxOne problem
Y=round(rand(n,s)); 

crossover.m

function Y=crossover(P,n)
% P = population
% n = number of pairs of chromosomes to be crossovered
[x1 y1]=size(P);
Z=zeros(2*n,y1); 
for i = 1:n
    r1=randi(x1,1,2);
    while r1(1)==r1(2)
        r1=randi(x1,1,2);
    end
    A1=P(r1(1),:); % parent 1
    A2=P(r1(2),:); % parent 2
    r2=1+randi(y1-1); % random cutting point
    B1=A1(1,r2:y1);
    A1(1,r2:y1)=A2(1,r2:y1);
    A2(1,r2:y1)=B1;
    Z(2*i-1,:)=A1; % offspring 1
    Z(2*i,:)=A2; % offspring 2
end
Y=Z;

mutation.m

function Y=mutation(P,n)
% P = population
% n = chromosomes to be mutated
[x1 y1]=size(P);
Z=zeros(n,y1);
for i = 1:n
    r1=randi(x1);
    A1=P(r1,:); % random parent
    r2=randi(y1);
    if A1(1,r2)== 1
        A1(1,r2) = 0; % flick the bit
    else
        A1(1,r2) = 1;
    end
    Z(i,:)=A1;
end
Y=Z;

GA.m

clear all
close all
clc
%--------------------------------------------------------------------------
p=100; % Population size
c=30; % number of pairs of chromosomes to be crossovered
m=20; % number chromosomes to be mutated
tg=500; % Total number of generations 

s= 50; % s= size of the MaxOne problem
%--------------------------------------------------------------------------
figure
title('Blue - Average         Red - Maximum');
xlabel('Generation')
ylabel('Objective Function Value')
hold on
P=population(p,s);
K=0;
[x1 y1]=size(P);
P1 = 0;
for i=1:tg   
    Cr=crossover(P,c);
    Mu=mutation(P,m);
.
.
.
Sorry! This is only a half of the Matlab code. 

Notice: It would take you from 1 to 3 hours to re-type the Matlab code yourself; or with just €2.99 (the cost of a cup of coffee), you can download/copy the whole Matlab code within 2 minutes. It’s your choice to make.

Original price is €5.99 but today it’s only €2.99 (save €3 today – available for a limited time only)

Download the whole Matlab code here (Membership Code ID: 034)

No need to build the Matlab code from scratch because it’s very time-consuming. My idol, Jim Rohn, once said: “Time is more value than money. You can get more money, but you cannot get more time”. If you think this code can be used in your research/teaching work, you should download it and then customize/modify/apply it to your work, without any obligation of citing the original source if you don’t want. However, redistribution (i.e., downloading the code/script here and then making it available on another site on the Internet) is strictly prohibited.

If you have any question or problem, please contact Dr. Panda by email: learnwithpanda2018@gmail.com

Thank you very much and good luck with your research and publications!