단순 유전 알고리즘 의 작은 예

6250 단어 인공지능
나 는 다른 사람 이 쓴 유전 알고리즘 자바 코드 를 약간 수정 했다.(원문 문서 에서 코드 의 출처 를 찾 을 수 있 습 니 다.)그것 도 간단 한 유전 알고리즘 의 기본 기능 을 실현 했다.이 코드 의 주석 은 비교적 많다.나 는 이 코드 의 조리 가 비교적 뚜렷 하 다 고 생각한다.잘 부탁드립니다.이 코드 는 주로 이 두 편의 글 에서 취재 한 것 이다. 주 체 는 다음 과 같다.http://www.cnblogs.com/macula7/archive/2009/04/04/1960673.html룰렛 도박 알고리즘 은:http://www.cnblogs.com/heaad/archive/2010/12/23/1914725.html이 코드 의 프로그램 프로 세 스 도 는 다음 과 같다. (이것 은 간단 한 유전 알고리즘 의 구조 이다)
简单遗传算法的小例子_第1张图片
/*A given function is as follows:
Use genetic algorithm to find a near-maximal value in f=xsin(10*pi*x)+2 
x     [-1,2]. 
In addition, the required precision is six places after the decimal point.
 */
import java.util.Random;

public class GA {
	public static final double A = -1;                 //      
	public static final double B = 2;                  //      
	public static Best best;                           //          
	public static final int POP_SIZE = 30;             //     (      30   ( x)  )
	public static String[] pop = new String[POP_SIZE];    // String   ,         ( x)   
	public static double[] result = new double[POP_SIZE]; // double   ,              ( x)
	public static double[] fitness = new double[POP_SIZE];//double ,         ( x)    
	public static final int LENGTH = 22; // x     ,            ,          (1 )     (6 )  7 。    22        。
	public static final int conversionFactor = 4194303;//    ,22                 2^22-1
	public static Random random = new Random();     //           
	public static final double PM = 0.05;           //    
	public static double[] p = new double[POP_SIZE];//             
	public static double[] q = new double[POP_SIZE];// q[i]  n p  
	int k1,k2;	//           	


	/*
	 *     ,     
	 */
	public GA(double d[]) {
		for (int i = 0; i < d.length; i++) {
			result[i] = d[i];
		}
	}
	
	/*
	 *      ,    ,    f(x)  ,x      。
	 */
	public void fitness() {
		for (int i = 0; i < result.length; i++) {
			fitness[i] = result[i] * (Math.sin(10 * Math.PI * result[i])) + 2;
			// System.out.println(fitness[i]);
		}
	}
	
	/*
	 *     ,              
	 */
	public void encoding()
	{
		for (int i = 0; i < result.length; i++) {
			//  result[i]     。
			//d1  :(|result[i] A    |/(      ))*    
			double d1 = ((result[i] - A) / (B - A)) * (conversionFactor);
			// d1       int ,             ,   pop   。
			pop[i] = Integer.toBinaryString((int) d1);
		}
		//    pop      ,      !=22,     “0”    22 
		for (int i = 0; i < pop.length; i++) {
			if (pop[i].length() < LENGTH) {
				int k = LENGTH - pop[i].length();
				for (int j = 0; j < k; j++) {
					pop[i] = "0" + pop[i];
				}
			}
		}
	}
	
	/*
	 *     ,                     。
	 */
	public void selection()
	{
		int k1;
		int k2;
		do {
			k1 = roulettewheel();
			k2 = roulettewheel();
		} while (k1 != k2);
	}
	
	/*
	 *      ,                。
	 */
	int roulettewheel()
	{
	    double m = 0;
	    double r =random.nextDouble(); //r 0 1    
	    int i = 0;
	    for(i=0;i<=LENGTH; i++)
	    {
	            /*        m~m+P[i]       i
	             *    i       P[i]
	             */
	             m = m + fitness[i];
	             if(r<=m)
	            	 break;
	    }
	    return i;
	}
	
	/*
	 *     ,         
	 */
	public void decoding() {
		for (int i = 0; i < pop.length; i++) {
			int k = Integer.parseInt(pop[i], 2);
			result[i] = A + k * (B - A) / (conversionFactor);
		}
	}

	/*
	 *     
	 */
	public void crossover() {
		//                 
		int position = random.nextInt(LENGTH);
		//s1      s11 s12,s2      s21,s22
		String s11 = null, s12 = null, s21 = null, s22 = null;
		s11 = pop[k1].substring(0, position);
		s12 = pop[k1].substring(position, LENGTH);
		s21 = pop[k2].substring(0, position);
		s22 = pop[k2].substring(position, LENGTH);
		//       ,     
		pop[k1] = s11 + s22;
		pop[k2] = s21 + s12;
	}

	/*
	 *     ,                 
	 */
	public void mutation() {
		// i   (    )
		for (int i = 0; i < pop.length; i++) {
			// i    j   
			for (int j = 0; j < LENGTH; j++) {
				double k = random.nextDouble();
				//        k     ,       。
				if (PM > k) {
					mutation(i, j);
				}
			}
		}
	}
	//        “1”   “0”。        “0”   “1”。
	public void mutation(int i, int j) {
		String s = pop[i];
		StringBuffer sb = new StringBuffer(s);
		if (sb.charAt(j) == '0')
			sb.setCharAt(j, '1');
		else
			sb.setCharAt(j, '0');
		pop[i] = sb.toString();

	}
	
	/*
	 *     
	 */
	public void evolution() {
		fitness();          //     
		encoding();         //  
		selection();        //  
		crossover();        //  
		mutation();         //  
		decoding();         //  
	}

	/*
	 *       ,n        
	 */
	public void dispose(int n) {
		for (int i = 0; i < n; i++) {
			evolution();
		}
	}

	/*
	 *     
	 */
	public double findBestOne() {
		if (best == null)
			best = new Best();
		double max = 0;
		for (int i=0;i max) {
				max = fitness[i];
				best.fitness = max;
				best.x = result[i];
				best.str = pop[i];
			}
		}
		return max;
	}
	
	/*
	 *          
	 */
	class Best { 
		public int generations;
		public String str;
		public double fitness;
		public double x;
	}

	public static void main(String[] args) {
		// d     
		double d[] = { -0.953181, -0.851234, -0.749723, -0.645386, -0.551234,
				-0.451644, -0.351534, -0.239566, -0.151234, 0.145445, 0.245445,
				0.285174, 0.345445, 0.445445, 0.542445, 0.645445, 0.786445,
				0.845445, 0.923238, 1.245445, 1.383453, 1.454245, 1.584566,
				1.644345, 1.741545, 1.845445, 1.981254, -0.012853, 0.083413,
				1.801231 };
		//             
		GA ga = new GA(d);
		System.out.println("     ....");
		//   ,    10000 
		ga.dispose(10000);
		ga.findBestOne();       //    
		System.out.println("+++++++++++++++++++++++++++   :");
		System.out.println("x=" + best.x);
		System.out.println("f=" + best.fitness);
		//for(double i :result)
		//{
		//	System.out.println(i);
		//}
	}
}

좋은 웹페이지 즐겨찾기