marcus2039
Freemium Model Innovator
2
MONTHS
2 2 MONTHS OF SERVICE
LEVEL 1
300 XP
In this article you will find a description of basic steps of the genetic Algorithm and an example of function's optimization in Java.
There is a variety of problems that can not be solved with a simple algorithms. This problems needs a lot of time and resources to find a solution. Often we don't have a to find an exact solution : we can find a solution that is enough good for the goal.
An example of such a kind of algorithm is Genetic Algorithm. Genetic algorithm is inspired by the process of the evolution in nature. The process of evolution shows that the nature created perfect things from the basic particles. The some thing is done by the genetic algorithm: a good solution can be found without having a lot of knowledge in the problem's area.
The Genetic algorithm consists of these steps:
One of the basic example of the use of the Genetic algorithm is soving the problem of function optimization - finding the minimum or the maximum value of a function on a interval.
I'll explain the Algorithm on this example.
First of all, a population is a set of "individuals", so we need to create individual
class:
This has a representation of an integer in decimal and binary form. Binary form is used for crossover operation. The crossover operation consists of dividing an individual's set of chromosomes (binary representation) and changing the part of genetic information between to individuals.
Population is a set of individuals. It can be implemented in next way:
These class performs next functions:
Now we have all data to implement the Genetic Algorithm. The basic cycle of the algorithm is:
nPopulation is number of populations, set by user and the workTime is the limit on execution time.
These is a basic example of the usage of Genetic Algorithm, but this algorithm can be applied to the range of problems from ,bioinformatics, , computational science, engineering, economics, chemistry, mathematics, physics and a lot of other areas.
You can download the example of this program and try it to find maximum of any function.
Download
There is a variety of problems that can not be solved with a simple algorithms. This problems needs a lot of time and resources to find a solution. Often we don't have a to find an exact solution : we can find a solution that is enough good for the goal.
An example of such a kind of algorithm is Genetic Algorithm. Genetic algorithm is inspired by the process of the evolution in nature. The process of evolution shows that the nature created perfect things from the basic particles. The some thing is done by the genetic algorithm: a good solution can be found without having a lot of knowledge in the problem's area.
The Genetic algorithm consists of these steps:
- Creating initial population
- Selection of individuals from the population
- "Mating"
- Crossover
- Checking if the solution is found
One of the basic example of the use of the Genetic algorithm is soving the problem of function optimization - finding the minimum or the maximum value of a function on a interval.
I'll explain the Algorithm on this example.
First of all, a population is a set of "individuals", so we need to create individual
class:
- package
optimisation_GA
;
- public
class
individual {
- int
decimal;
- String
binary;
- int
fitnessFunction;
- int
length;
//length of binary representation
- individual(
int
value, int
_length)
{
- decimal =
value;
- length =
_length;
- binary =
""
;
- decToBin(
decimal)
;
- addZero(
)
;
- }
- //makes binary representation of each
- //decimal of equal length
- private
void
addZero(
)
{
- // TODO Auto-generated method stub
- for
(
int
i =
binary.length
(
)
;
i !=
length;
++
i)
- binary =
"0"
+
binary;
- }
- //convert from decimal number
- //to binary number
- private
Object
decToBin(
int
dec)
{
- // TODO Auto-generated method stub
- int
num;
- if
(
dec <=
1
)
{
- binary +=
dec;
- return
null
;
// KICK OUT OF THE RECURSION
- }
- num=
dec %
2;
- decToBin(
dec >>
1
)
;
- binary +=
num;
- return
null
;
- }
- public
individual crossover(
individual pair)
{
- individual child;
- int
crossoverPoint =
(
int
)
Math
.random
(
)
*
length;
- String
newBinValue =
""
;
- for
(
int
i =
0
;
i !=
crossoverPoint;
++
i)
- newBinValue +=
binary.charAt
(
i)
;
- for
(
int
i =
crossoverPoint;
i !=
length;
++
i)
- newBinValue +=
binary.charAt
(
i)
;
- child =
new
individual(
Integer
.parseInt
(
newBinValue,2
)
,length)
;
- return
child;
- }
- }
This has a representation of an integer in decimal and binary form. Binary form is used for crossover operation. The crossover operation consists of dividing an individual's set of chromosomes (binary representation) and changing the part of genetic information between to individuals.
Population is a set of individuals. It can be implemented in next way:
- package
optimisation_GA
;
- import
java.util.ArrayList
;
- import
java.util.Collections
;
- import
java.util.Comparator
;
- import
javax.script.ScriptEngine
;
- import
javax.script.ScriptEngineManager
;
- import
javax.script.ScriptException
;
- import
javax.swing.JOptionPane
;
- public
class
population {
- int
a;
- int
b;
- int
numberOfPopulation;
- int
size;
- int
timeLimit;
- int
length;
- String
function;
- ArrayList<
individual>
individuals;
- population(
String
_function,int
_a,int
_b,int
_numberOfPopulation,int
_size,int
_timeLimit,int
_length)
{
- individuals =
new
ArrayList<
individual>
(
)
;
- function =
_function;
- a =
_a;
- b =
_b;
- numberOfPopulation =
_numberOfPopulation;
- size =
_size;
- timeLimit =
_timeLimit;
- length =
_length;
- initialPopulation(
)
;
- }
- private
void
initialPopulation(
)
{
- // TODO Auto-generated method stub
- for
(
int
i =
0
;
i !=
size;
++
i)
{
- int
rand =
a +
(
int
)
(
Math
.random
(
)
*
(
(
b -
a)
+
1
)
)
;
- individuals.add
(
new
individual(
rand,length)
)
;
- }
- }
- public
void
calculateFitnessFunction(
)
{
- for
(
int
i =
0
;
i !=
individuals.size
(
)
;++
i)
{
- int
x =
individuals.get
(
i)
.decimal
;
- String
tempValue =
function;
- String
replaceSt =
Integer
.toString
(
x)
;
- String
testValue =
tempValue.replace
(
"x"
, Integer
.toString
(
x)
)
;
- ScriptEngineManager mgr =
new
ScriptEngineManager(
)
;
- ScriptEngine engine =
mgr.getEngineByName
(
"JavaScript"
)
;
- try
{
- int
y =
(
(
Double
)
engine.eval
(
testValue)
)
.intValue
(
)
;
- individuals.get
(
i)
.fitnessFunction
=
y;
- }
catch
(
ScriptException e1)
{
- // TODO Auto-generated catch block
- }
- }
- }
- public
void
range(
)
{
- Collections
.sort
(
individuals, new
Comparator<
individual>
(
)
{
- public
int
compare(
individual left, individual right)
{
- return
right.fitnessFunction
-
left.fitnessFunction
;
- }
- }
)
;
- for
(
int
i =
0
;
i !=
individuals.size
(
)
;++
i)
- System
.out
.println
(
individuals.get
(
i)
.decimal
+
" -- "
+
individuals.get
(
i)
.fitnessFunction
)
;
- }
- public
void
selection(
)
{
- // TODO Auto-generated method stub
- if
(
individuals.size
(
)
==
size)
- return
;
- while
(
individuals.size
(
)
>
size)
- individuals.remove
(
individuals.size
(
)
-
1
)
;
- }
- public
void
crossover(
)
{
- // TODO Auto-generated method stub
- for
(
int
i =
0
;
i !=
size;++
i)
{
- individual child =
individuals.get
(
i)
.crossover
(
getRandomIndividual(
)
)
;
- individuals.add
(
child)
;
- }
- }
- private
individual getRandomIndividual(
)
{
- return
individuals.get
(
(
int
)
Math
.random
(
)
*
size)
;
- }
- public
void
printP(
)
{
- // TODO Auto-generated method stub
- for
(
int
i =
0
;
i !=
individuals.size
(
)
;++
i)
- System
.out
.println
(
i +
" "
+
individuals.get
(
i)
.decimal
+
" -- "
+
individuals.get
(
i)
.fitnessFunction
)
;
- }
- }
These class performs next functions:
- creates initial population. It's done by generating a number of random individuals in interval of function definition.
- calculates fitness function. Fitness function is a value, that shows, how is the individual is "accommodated" to the environmental conditions. In this example fitness function is the function that needs to be optimazed
- ranges individuals of population according to the fitness function value
- selects the best individuals from population after ranging them by the fitness function.
Now we have all data to implement the Genetic Algorithm. The basic cycle of the algorithm is:
- workingPopulation =
new
population(
functionString,a,b,nPopulation,size,time,length)
;
- int
count =
0
;
- long
startTime,
- endTime,
- workTime;
- startTime =
System
.currentTimeMillis
(
)
/
1000
;
- workingPopulation.calculateFitnessFunction
(
)
;
- do
{
- workingPopulation.selection
(
)
;
- System
.out
.println
(
"Selection passed"
)
;
- workingPopulation.crossover
(
)
;
- System
.out
.println
(
"crossover passed"
)
;
- workingPopulation.calculateFitnessFunction
(
)
;
- workingPopulation.range
(
)
;
- count++;
- endTime =
System
.currentTimeMillis
(
)
/
1000
;
- workTime =
endTime -
startTime;
- System
.out
.println
(
"-------------------generation #"
+
count+
1
)
;
- workingPopulation.printP
(
)
;
- }
while
(
(
workTime <
time)
&&
(
count <
nPopulation)
)
;
- workingPopulation.printP
(
)
;
nPopulation is number of populations, set by user and the workTime is the limit on execution time.
These is a basic example of the usage of Genetic Algorithm, but this algorithm can be applied to the range of problems from ,bioinformatics, , computational science, engineering, economics, chemistry, mathematics, physics and a lot of other areas.
You can download the example of this program and try it to find maximum of any function.
Download
You must upgrade your account or reply in the thread to view hidden text.