遗传算法_遗传算法中选择的方法

   
   

    
    
    
    /*
* 按设定的概率，随机选中一个个体
* P[i]表示第i个个体被选中的概率
*/
int RWS()
{
    m = 0;
    r =Random(0,1); //r为0至1的随机数
    for(i=1;i<=N; i++)
    {
            /* 产生的随机数在m~m+P[i]间则认为选中了i
             *  因此i被选中的概率是P[i]
             */
             m = m + P[i];
             if(r<=m) return i;
    }
}
   
   

   
   

    
    
    
    /*
* Pc：交叉发生的概率
* Pm：变异发生的概率
* M：种群规模
* G：终止进化的代数
* Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程
*/
初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Pop
 
do
{     
　　计算种群Pop中每一个体的适应度F(i)。
　　初始化空种群newPop
　　do
　　{
　　　　根据适应度以比例选择算法从种群Pop中选出2个个体
　　　　if ( random ( 0 , 1 ) < Pc )
　　　　{
　　　　　　对2个个体按交叉概率Pc执行交叉操作
　　　　}
　　　　if ( random ( 0 , 1 )  < Pm )
　　　　{
　　　　　　对2个个体按变异概率Pm执行变异操作
　　　　}
       将2个新个体加入种群newPop中
    } until ( M个子代被创建 )
    用newPop取代Pop
}until ( 任何染色体得分超过Tf， 或繁殖代数超过G )
   
   
   
   

    
    

   
   

   
   

    
    
    
    using System;
using AForge.Genetic;

namespace GenticTSP
{
    /// <summary>
    /// Fitness function for TSP task (Travaling Salasman Problem)
    /// </summary>
    public class TSPFitnessFunction : IFitnessFunction
    {
        // map
        private int[,] map = null;

        // Constructor
        public TSPFitnessFunction(int[,] map)
        {
            this.map = map;
        }

        /// <summary>
        /// Evaluate chromosome - calculates its fitness value
        /// </summary>
        public double Evaluate(IChromosome chromosome)
        {
            return 1 / (PathLength(chromosome) + 1);
        }

        /// <summary>
        /// Translate genotype to phenotype 
        /// </summary>
        public object Translate(IChromosome chromosome)
        {
            return chromosome.ToString();
        }

        /// <summary>
        /// Calculate path length represented by the specified chromosome 
        /// </summary>
        public double PathLength(IChromosome chromosome)
        {
            // salesman path
            ushort[] path = ((PermutationChromosome)chromosome).Value;

            // check path size
            if (path.Length != map.GetLength(0))
            {
                throw new ArgumentException("Invalid path specified - not all cities are visited");
            }

            // path length
            int prev = path[0];
            int curr = path[path.Length - 1];

            // calculate distance between the last and the first city
            double dx = map[curr, 0] - map[prev, 0];
            double dy = map[curr, 1] - map[prev, 1];
            double pathLength = Math.Sqrt(dx * dx + dy * dy);

            // calculate the path length from the first city to the last
            for (int i = 1, n = path.Length; i < n; i++)
            {
                // get current city
                curr = path[i];

                // calculate distance
                dx = map[curr, 0] - map[prev, 0];
                dy = map[curr, 1] - map[prev, 1];
                pathLength += Math.Sqrt(dx * dx + dy * dy);

                // put current city as previous
                prev = curr;
            }

            return pathLength;
        }
    }
}

   
   

   
   

    
    
    
    using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

using AForge;
using AForge.Genetic;


namespace GenticTSP
{
    class GenticTSP
    {

        static void Main()
        {
            StreamReader reader = new StreamReader("Data.txt");

            int citiesCount = 31;  //城市数

            int[,] map = new int[citiesCount, 2];

            for (int i = 0; i < citiesCount; i++)
            {
                string value = reader.ReadLine();
                string[] temp = value.Split(' ');
                map[i, 0] = int.Parse(temp[0]);  //读取城市坐标
                map[i, 1] = int.Parse(temp[1]);
            }

            // create fitness function
            TSPFitnessFunction fitnessFunction = new TSPFitnessFunction(map);

            int populationSize = 1000;  //种群最大规模

            /*  
             * 0：EliteSelection算法 
             * 1：RankSelection算法  
             * 其他：RouletteWheelSelection 算法
             * */
            int selectionMethod = 0;

            // create population
            Population population = new Population(populationSize,
                new PermutationChromosome(citiesCount),
                fitnessFunction,
                (selectionMethod == 0) ? (ISelectionMethod)new EliteSelection() :
                (selectionMethod == 1) ? (ISelectionMethod)new RankSelection() :
                (ISelectionMethod)new RouletteWheelSelection()
                );

            // iterations
            int iter = 1;
            int iterations = 5000;  //迭代最大周期

            // loop
            while (iter < iterations)
            {
                // run one epoch of genetic algorithm
                population.RunEpoch();

                // increase current iteration
                iter++;
            }

            System.Console.WriteLine("遍历路径是： {0}", ((PermutationChromosome)population.BestChromosome).ToString());
            System.Console.WriteLine("总路程是：{0}", fitnessFunction.PathLength(population.BestChromosome));
            System.Console.Read();

        }
    }
}