public partial class yichuansf2 : System.Web.UI.Page
{
    protected void Page_Load(object sender, EventArgs e)
    {

    }
    public class yichuansuanfa
    {
        public int clientnumber=9;//城市数
        public int popsize=100;//种群数
        public int m;
        public int Q=5;//车辆载重限制
        private double CrossoverRate=0.55;//交叉率
        private double MutationRate=0.05;//变异率
        public int[,] Chromosomes;//染色体数组
        public int curGeneration;
        public double[] Distance;
        public double[] IndividualFitness;
        public double[] SelectedRate;
        public double[] AddSelectedRate;
        public double BestValue;
        public int[] Bestroad;
        public int[] BestIndividual;
        public int Bestindex;
        public double BestFitness;
        public DataTable table;
        public double[] clientX ={ 2500, 2300, 1500, 3000, 1600, 3000, 2300, 2000, 1400 };
        public double[] clientY ={ 2500, 2500, 2000, 1000, 2200, 2000, 1600, 1500, 2100 };
        public double[] xuqiu ={0, 2, 2, 1, 4, 3, 1, 2, 2 };
      

      
        public void InitPath()
        {
            SelectedRate = new double[popsize];
            AddSelectedRate = new double[popsize];
            Chromosomes = new int[popsize, clientnumber + m];
            Distance = new double[popsize];
            IndividualFitness = new double[popsize];
            BestIndividual = new int[clientnumber + m];
            Bestroad = new int[clientnumber + m];


        }
        public void minvehicle()
        {
            int m = 0;
            double Sumxuqiu = 0;           //Q为车辆载重限制

            for (int i = 0; i < clientnumber; i++)
                Sumxuqiu += xuqiu[i];
            if (0 < Q)    //Q为零不能除
            {
                if (Sumxuqiu % Q != 0)
                {
                    m = (int)Sumxuqiu / Q + 1;
                }
                else
                {
                    m = (int)Sumxuqiu / Q;        //m为最少车辆数
                }
            }
        }

        public void InitChromosomes()
        {
            int[] Spring = new int[clientnumber + m];
            for (int i = 0; i < popsize; )
            {
                Random rand = new Random();
                for (int j = 0; j < (clientnumber + m); j++)
                {
                    Spring[j] = 1200;           //初始化spring
                }
                Spring[0] = 0;        //在排列的开头插入0
                for (int j = 1; j < clientnumber; j++)
                {
                    Spring[j] = rand.Next(0, clientnumber);

                    for (int k = 0; k < j; )
                    {
                        if (Spring[j] != Spring[k])
                        {
                            k++;
                            continue;
                        }
                        else   //先编完自然数排列，才插入0，最后判断是否为可行解
                        {
                            do
                            {
                                Spring[j] = rand.Next(0, clientnumber);
                            } while (Spring[j] == Spring[k]);
                            k = 0;
                        }
                    }
                }
                int x = 0;
                //在排列中除去前后位置随机选择位置插入0
                for (int n = 0; n < m - 1; n++)            //m为最少车辆数
                {
                    x = rand.Next(0, clientnumber + n);
                    for (int j = clientnumber + n; j > x; j--)
                        Spring[j] = Spring[j - 1];
                    Spring[x] = 0;
                }
                //在自然数的排列中最后插入0
                Spring[clientnumber + m - 1] = 0;

                //车辆载重限制
                double Sumxuqiu = 0;
                for (int j = 0; j < clientnumber + m; j++)
                {
                    if (Spring[j] == 0)
                    {
                        if (Sumxuqiu <= Q)
                        {
                            Sumxuqiu = 0;
                            if (j == clientnumber + m - 1)
                            {
                                for (int l = 0; l < clientnumber + m; l++)
                                    Chromosomes[i,l] = Spring[l];//若符合限制，则复制到Chromosomes数组中
                                i++;
                                break;
                            }
                            continue;
                        }
                        else
                        {
                            break;
                        }
                    }
                    else
                    {
                        if (Spring[j] < clientnumber)
                            Sumxuqiu += xuqiu[Spring[j]];
                        continue;
                    }
                }
            }
        }

        //计算个体适值
        public void CaculateFitness()
        {
            double x1 = 0;
            double x2 = 0;
            double y1 = 0;
            double y2 = 0;
            for (int i = 0; i < popsize; i++)
            {
                double sum = 0;
                for (int j = 0; j < clientnumber + m-1; j++)
                {
                    if ((Chromosomes[i, j] < clientnumber) && (Chromosomes[i, j + 1] < clientnumber))
                    {
                        x1 = clientX[Chromosomes[i, j]];
                        x2 = clientX[Chromosomes[i, j + 1]];
                        y1 = clientY[Chromosomes[i, j]];
                        y2 = clientY[Chromosomes[i, j + 1]];
                        sum += Math.Sqrt((double)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
                    }
                }
                Distance[i] = sum;
                IndividualFitness[i] = (double)1.0 / Distance[i];   //个体适应度函数值
            }
            BestFitness = IndividualFitness[0];
            BestValue = Distance[0];
        }
        //计算个染色体的选择概率
        public void CaculateSelectedRate()
        {
            CaculateFitness();
            double sum = 0;
            for (int i = 0; i < popsize; i++)
                sum += IndividualFitness[i];
            for (int i = 0; i < popsize; i++)
            {
                SelectedRate[i] = IndividualFitness[i] / sum;
            }
        }
        //计算个染色体的累计选择概率
        public void CalAddSelectedRate()
        {
            for (int i = 0; i < popsize; i++)
            {
                AddSelectedRate[i] = 0.0;
                for (int k = 0; k <= i; k++)
                    AddSelectedRate[i] += SelectedRate[k];
            }
        }
        //寻找最好的个体
        public void FindBestIndividual()
        {
            CaculateFitness();
            for (int x = 1; x < popsize; x++)
            {
                if (IndividualFitness[x] > BestFitness)
                {
                    BestFitness = IndividualFitness[x];    //最优适应度函数值：最大
                  
                }
            }
            for (int x = 1; x < popsize; x++)
            {
                if (BestValue > Distance[x])
                {
                    BestValue = Distance[x];    //记录最优路径距离值：最小距离
                    Bestindex = x;
                }
               
            }
            if (popsize > Bestindex)
            {
                for (int j = 0; j < clientnumber + m; j++)
                    BestIndividual[j] = Chromosomes[Bestindex, j];   //记录最优路径
            }
        }
        //选择操作
        public void SelectedOperator()
        {
            int index = 0;
            double Ri = 0.0;
            Random rand = new Random();
            int[,] OffSpring = new int[popsize, clientnumber + m];
            //求出种群中适应度最大的个体，将其作为下一代的个体，即最优个体必遗传到下一代
            if (popsize > Bestindex)
            {
                for (int j = 0; j < clientnumber + m; j++)
                {
                    OffSpring[0, j] =Chromosomes[Bestindex, j];
                }
            }
            //计算每个个体的选择概率
            CaculateSelectedRate();
            //计算每个个体的累加概率
            CalAddSelectedRate();
            //产生popsize个[0,1)间的分布的随机数Ri，若S(K-1)<Ri<S(K)，则选择个体为K为下代个体,若不在范围内则选则最优个体
            for (int i = 1; i < popsize; i++)
            {
                Ri = rand.NextDouble();
                if (Ri < AddSelectedRate[0])
                    index = 0;
                else
                    for (int k = 1; k < popsize; k++)
                        if (Ri > AddSelectedRate[k - 1] && Ri <= AddSelectedRate[k])
                            index = k;
                for (int j = 0; j < clientnumber + m; j++)
                    OffSpring[i, j] = Chromosomes[index, j];
            }
            for (int i = 0; i < popsize; i++)
                for (int j = 0; j < clientnumber + m; j++)
                    Chromosomes[i, j] = OffSpring[i, j];    //生成新的第二代种群

        }
        //交叉操作
        public void CrossOverOperator()
        {
            Random random = new Random();
            double[] pc = new double[popsize];
            int[] crossoverindividual = new int[popsize];
            int index = 0;
            int[] offspring1 = new int[clientnumber + m];
            int[] offspring2 = new int[clientnumber + m];
            int point11 = 0, point12 = 0, point21 = 0, point22 = 0;
            ArrayList al = new ArrayList();
            for (int i = 0; i < popsize; i++)
            {
                pc[i] = random.NextDouble();          //生成种群个0-1随机数作为交叉概率
            }
            for (int i = 0; i < popsize; i++)
            {
                if (pc[i] < CrossoverRate)
                {
                    crossoverindividual[index] = i;   //选择整个种群用于交叉的染色体i
                    al.Add((object)i);
                    index++;
                }
            }

            if (index % 2 != 0)
            {
                index = index - 1;                    //取成双的对数进行交叉
            }
            for (int i = 0; i < index - 1; i += 2)
            {
                for (int j = 0; j < clientnumber + m; j++)
                {
                    offspring1[j] = 1000;           //初始化offspring1和2
                    offspring2[j] = 1000;
                }
                if (2 < clientnumber + m)
                {
                    point11 = random.Next(clientnumber + m - 2);
                    do
                    {
                        point12 = random.Next(clientnumber + m);   //交叉11点小于交叉12点
                    } while (point11 >= point12);
                    point21 = random.Next(clientnumber + m - 2);
                    do
                    {
                        point22 = random.Next(clientnumber + m);   //交叉21点小于交叉22点
                    } while (point21 >= point22);
                }
                //记录下父代的子串
                for (int k = point11 + 1; k < point12; k++)
                {
                    if (Chromosomes[crossoverindividual[i], point11] == 0 && Chromosomes[crossoverindividual[i], point12] == 0)
                    {
                        offspring1[k] = Chromosomes[crossoverindividual[i], k];    //父亲染色体用于交叉的染色体的交叉子串

                    }
                    else
                    {
                        if (Chromosomes[crossoverindividual[i], point12] != 0)
                        {
                            do
                            {
                                point12++;
                            } while (Chromosomes[crossoverindividual[i], point12] != 0);
                        }
                        if (Chromosomes[crossoverindividual[i], point11] != 0)
                        {
                            do
                            {
                                point11++;
                            } while (Chromosomes[crossoverindividual[i], point11] != 0);
                            if (point11 >= point12)
                            {
                                do
                                {
                                    point11--;
                                } while (Chromosomes[crossoverindividual[i], point11] != 0 && 0<point11);
                            }
                        }
                    }

                }
                //记录下母代的子串
                for (int k = point21 + 1; k < point22; k++)
                {
                    if (Chromosomes[crossoverindividual[i + 1], point21] == 0 && Chromosomes[crossoverindividual[i + 1], point22] == 0)
                    {
                        offspring2[k] = Chromosomes[crossoverindividual[i + 1], k];    //母亲染色体用于交叉的染色体的交叉子串

                    }
                    else
                    {
                        if (Chromosomes[crossoverindividual[i + 1], point22] != 0)
                        {
                            do
                            {
                                point22++;
                            } while (Chromosomes[crossoverindividual[i + 1], point22] != 0);
                        }
                        if (Chromosomes[crossoverindividual[i + 1], point21] != 0)
                        {
                            do
                            {
                                point21++;
                            } while (Chromosomes[crossoverindividual[i + 1], point21] != 0);
                            if (point21 >= point22)
                            {
                                do
                                {
                                    point21--;
                                } while (Chromosomes[crossoverindividual[i + 1], point21] != 0 && 0 < point21);
                            }
                        }
                    }

                }

                for (int j = 0; j < clientnumber + m; j++)
                {
                    if (Chromosomes[crossoverindividual[i], j] == 0)    //保留父亲0的位置和0
                        offspring1[j] = 0;
                }
                for (int j = 0; j < clientnumber + m; j++)
                {
                    if (Chromosomes[crossoverindividual[i + 1], j] == 0)    //保留母亲0的位置和0
                        offspring2[j] = 0;
                }

                //填充其余字串,将父亲的其余字串填充到母亲的子染色体中，将母亲的其余字串填充到父亲的子染色体中
                int Temp1 = 0, Temp2 = 0;
                Temp1 = clientnumber - point12 + point11;
                Temp2 = clientnumber - point22 + point21;
                int[] offspring11 = new int[Temp1];
                int[] offspring22 = new int[Temp2];
                int m1=0;
                int m2=0;
                for (int k = point11 + 1; k < point12; k++)
                {
                    for (int j = 0; j < clientnumber + m; j++)
                    {
                        if ((Chromosomes[crossoverindividual[i + 1], j] != offspring1[k]) && Chromosomes[crossoverindividual[i + 1], j] != 0)
                        {
                            for (; m1 < Temp1; m1++)
                            {  
                                offspring11[m1] = Chromosomes[crossoverindividual[i + 1], j];      //按顺序记录母亲染色体非交叉子串的编
                            }
                        }
                    }
                }

                for (int l = 0; l < m1; l++)
                {
                    for (int j = 0; j < clientnumber + m; j++)
                    {
                        if (offspring1[j] ==1000)
                        {
                           offspring1[j] = offspring11[l];
                           break;
                        }
                    }
                }
                for (int k = point21 + 1; k < point22; k++)
                {
                    for (int j = 0; j < clientnumber + m; j++)
                    {
                        if ((Chromosomes[crossoverindividual[i], j] != offspring2[k]) && Chromosomes[crossoverindividual[i], j] != 0)
                        {
                            for (; m2 < Temp2; m2++)
                            {   
                                 offspring22[m2] = Chromosomes[crossoverindividual[i], j];      //按顺序记录父亲染色体非交叉子串的编码
                            }
                        }
                    }
                }
                for (int p = 0; p < m2; p++)
                {
                    for (int j = 0; j < clientnumber + m; j++)
                    {
                         if (offspring2[j] == 1000)
                         {
                             offspring2[j] = offspring22[p];
                             break;
                         }
                    }
                }
                //判定子染色体是否为可行解，车辆载重限制
                double Sumxuqiu1 = 0;
                for (int j = 0; j < clientnumber + m; j++)
                {
                    if (offspring1[j] == 0)
                    {
                        if (Sumxuqiu1 <= Q)
                        {
                            Sumxuqiu1 = 0;
                            continue;
                        }
                        else
                        {
                            //若子代不满足限制，则将父代复制到子代
                            for (int w = 0; w < clientnumber + m; w++)
                            {
                                offspring1[w] = Chromosomes[crossoverindividual[i], w];

                            }
                            break;
                        }
                    }
                    else
                    {
                        if (offspring1[j]<clientnumber)
                             Sumxuqiu1 += xuqiu[offspring1[j]];
                        continue;
                    }

                }
                double Sumxuqiu2 = 0;
                for (int j = 0; j < clientnumber + m; j++)
                {
                    if (offspring2[j] == 0)
                    {
                        if (Sumxuqiu2 <= Q)
                        {
                            Sumxuqiu2 = 0;
                            continue;
                        }
                        else
                        {
                            //若子代不满足限制，则将父代复制到子代
                            for (int w = 0; w < clientnumber + m; w++)
                            {
                                offspring2[w] = Chromosomes[crossoverindividual[i + 1], w];
                            }
                            break;
                        }
                    }
                    else
                    {
                        if (offspring2[j] < clientnumber)
                            Sumxuqiu2 += xuqiu[offspring2[j]];
                        continue;
                    }

                }
                //将子代复制回父代；
                for (int j = 0; j < clientnumber + m; j++)
                {
                    Chromosomes[crossoverindividual[i], j] = offspring1[j];
                    Chromosomes[crossoverindividual[i + 1], j] = offspring2[j];
                }

            }

        }
        /// <summary>
        /// 变异操作
        /// </summary>
        public void MutationOperator()
        {
            //思路：将个体编码串中随机选取的两个相邻非零基因座之间的基因逆序排列
            double[] pm = new double[popsize];
            int[] Mutationindividual = new int[popsize];
            int[] offspring3 = new int[clientnumber + m];
            int point1 = 0, point2 = 0;
            ArrayList bl = new ArrayList();
            Random rand = new Random();
            int index2 = 0;
            int temp;
            for (int i = 0; i < popsize; i++)
            {
                pm[i] = rand.NextDouble();          //生成种群个0-1随机数
            }
            for (int i = 0; i < popsize; i++)
            {
                if (pm[i] < MutationRate)
                {
                    Mutationindividual[index2] = i;   //选择整个种群用于变异的染色体i
                    bl.Add((object)i);
                    index2++;
                }
            }
            for (int i = 0; i < index2; i++)
            {
                if (2 < clientnumber+m)
                {
                    do
                    {
                        point1 = rand.Next(clientnumber + m - 2);
                        point2 = point1 + 1;
                    } while (Chromosomes[Mutationindividual[i], point1] != 0 && Chromosomes[Mutationindividual[i], point2] != 0);
                }
                temp = Chromosomes[Mutationindividual[i], point1];
                Chromosomes[Mutationindividual[i], point1] = Chromosomes[Mutationindividual[i], point2];
                Chromosomes[Mutationindividual[i], point2] = temp;           
            }
        }
   }
    protected void Button2_Click(object sender, EventArgs e)
    {

        yichuansuanfa ycsf = new yichuansuanfa();
        ycsf.InitPath();
        ycsf.minvehicle();
        ycsf.InitChromosomes();
        for (int i = 0; i < 250; i++)//迭代次数250
        {
            ycsf.CaculateFitness();
            ycsf.CaculateSelectedRate();
            ycsf.CalAddSelectedRate();
            ycsf.FindBestIndividual();
            ycsf.SelectedOperator();
            ycsf.CrossOverOperator();
            ycsf.MutationOperator();
  
        }
        TextBox8.Text = ycsf.m.ToString();//输出最少车辆数
        TextBox7.Text = ycsf.BestValue.ToString();//输出最佳路径值
        string str = "";
        for (int j = 0; j <ycsf.m+ycsf.clientnumber; j++)
        {
            string str1 = ycsf.BestIndividual[j].ToString();
            str += str1 + "->";
        }
        this.Label1.Text = str;//输出最佳路径
            }