Genetic Algorithm: Solving the Function Optimization Problem using Java

Submitted by pavel7_7_7 on Wednesday, February 12, 2014 - 09:29.
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:
  1. Creating initial population
  2. Selection of individuals from the population
  3. "Mating"
  4. Crossover
  5. 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: 
  1. package optimisation_GA;
  2.  
  3. public class individual {
  4. 	int decimal;
  5. 	String binary;
  6. 	int fitnessFunction;
  7. 	int length;//length of binary representation
  8. 	individual(int value, int _length){
  9. 		decimal = value;
  10. 		length = _length;
  11. 		binary = "";
  12. 		decToBin(decimal);
  13. 		addZero();
  14. 	}
  15. 	//makes binary representation of each
  16. 	//decimal of equal length
  17. 	private void addZero() {
  18. 		// TODO Auto-generated method stub
  19. 		for(int i = binary.length(); i != length; ++i)
  20. 			binary = "0" + binary;
  21.  
  22. 	}
  23. 	//convert from decimal number
  24. 	//to binary number
  25. 	private Object decToBin(int dec) {
  26. 		// TODO Auto-generated method stub
  27. 		int num;
  28.  
  29.         if (dec <=1) {
  30.             binary +=dec;
  31.             return null;   // KICK OUT OF THE RECURSION
  32.         }
  33.  
  34.         num= dec %2; 
  35.         decToBin(dec >>1);
  36.         binary += num;
  37.         return null;	
  38. 	}
  39. 	public individual crossover(individual pair){
  40. 		individual child;
  41. 		int crossoverPoint = (int)Math.random()*length;
  42. 		String newBinValue = "";
  43. 		for(int i = 0; i != crossoverPoint; ++i)
  44. 			newBinValue += binary.charAt(i);
  45. 		for(int i = crossoverPoint; i != length; ++i)
  46. 			newBinValue += binary.charAt(i);
  47. 		child = new individual(Integer.parseInt(newBinValue,2),length);
  48. 		return child;
  49. 	}
  50.  
  51. }
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: 
  1. package optimisation_GA;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.Collections;
  5. import java.util.Comparator;
  6.  
  7. import javax.script.ScriptEngine;
  8. import javax.script.ScriptEngineManager;
  9. import javax.script.ScriptException;
  10. import javax.swing.JOptionPane;
  11.  
  12. public class population {
  13. 	int a;
  14. 	int b;
  15. 	int numberOfPopulation;
  16. 	int size;
  17. 	int timeLimit;
  18. 	int length;
  19. 	String function;
  20.  
  21. 	ArrayList<individual> individuals;
  22. 	population(String _function,int _a,int _b,int _numberOfPopulation,int _size,int _timeLimit,int _length){
  23. 		individuals = new ArrayList<individual>();
  24. 		function = _function;
  25. 		a = _a;
  26. 		b = _b;
  27. 		numberOfPopulation = _numberOfPopulation;
  28. 		size = _size;
  29. 		timeLimit = _timeLimit;
  30. 		length = _length;
  31. 		initialPopulation();
  32. 	}
  33. 	private void initialPopulation() {
  34. 		// TODO Auto-generated method stub
  35. 		for(int i = 0; i != size; ++i){
  36. 			int rand = a + (int)(Math.random() * ((b - a) + 1));
  37. 			individuals.add(new individual(rand,length));
  38. 		}
  39. 	}
  40. 	public void calculateFitnessFunction(){
  41. 		for(int i = 0; i != individuals.size();++i){
  42. 			int x = individuals.get(i).decimal;
  43. 			String tempValue = function;
  44. 			String replaceSt = Integer.toString(x);
  45.  
  46. 			String testValue = tempValue.replace("x", Integer.toString(x));
  47. 			ScriptEngineManager mgr = new ScriptEngineManager();
  48. 			ScriptEngine engine = mgr.getEngineByName("JavaScript");
  49. 			try {
  50. 				int y = ((Double)engine.eval(testValue)).intValue();
  51. 				individuals.get(i).fitnessFunction = y;
  52. 			} catch (ScriptException e1) {
  53. 				// TODO Auto-generated catch block
  54.  
  55. 			}
  56. 		}
  57. 	}
  58. 	public void range(){
  59. 		Collections.sort(individuals, new Comparator<individual>() {
  60. 		    public int compare(individual left, individual right)  {
  61. 		        return right.fitnessFunction - left.fitnessFunction; 
  62. 		    }
  63. 		});
  64. 		for(int i = 0; i != individuals.size();++i)
  65. 			System.out.println(individuals.get(i).decimal + " -- " + individuals.get(i).fitnessFunction );
  66. 	}
  67. 	public void selection() {
  68. 		// TODO Auto-generated method stub
  69. 		if(individuals.size() == size)
  70. 			return;
  71. 		while(individuals.size() > size)
  72. 			individuals.remove(individuals.size() - 1);
  73.  
  74.  
  75. 	}
  76. 	public void crossover() {
  77. 		// TODO Auto-generated method stub
  78. 		for(int i = 0; i != size;++i){
  79. 			individual child = individuals.get(i).crossover(getRandomIndividual());
  80. 			individuals.add(child);
  81. 		}
  82.  
  83.  
  84. 	}
  85. 	private individual getRandomIndividual(){
  86. 		return individuals.get((int)Math.random()*size);
  87. 	}
  88. 	public void printP() {
  89. 		// TODO Auto-generated method stub
  90. 		for(int i = 0; i != individuals.size();++i)
  91. 			System.out.println(i + " " + individuals.get(i).decimal + " -- " + individuals.get(i).fitnessFunction );
  92. 	}
  93. }
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: 
  1. workingPopulation = new population(functionString,a,b,nPopulation,size,time,length);
  2. 			int 	count = 0;
  3. 			long	startTime,
  4. 					endTime,
  5. 					workTime;
  6. 			startTime = System.currentTimeMillis()/1000;
  7. 			workingPopulation.calculateFitnessFunction();
  8.  
  9. 			do{
  10. 				workingPopulation.selection();
  11. 				System.out.println("Selection passed");
  12. 				workingPopulation.crossover();
  13. 				System.out.println("crossover passed");
  14. 				workingPopulation.calculateFitnessFunction();
  15.  
  16. 				workingPopulation.range();
  17. 				count++;
  18. 				endTime = System.currentTimeMillis()/1000;
  19. 				workTime = endTime - startTime;
  20. 				System.out.println("-------------------generation #" +count+1);
  21. 				workingPopulation.printP();
  22.  
  23. 			}while((workTime < time) &&(count < nPopulation));
  24. 			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.

Tags

Add new comment

About text formats
  • 86 views