program.cs

遗传算法用于求解多目标背包问题

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1
{
    public class Genetic_Algorithm
    {
        Random rand;
        int MaxTime;

        int popsize;
        int ChromosomeLength;
        double CrossRate;//Crossover rate
        double MutateRate;

        double capacity1;
        double capacity2;
        double[] v;
        double[] w1;
        double[] w2;
        double[] f;//fitness

        int[] selected;
        double[] wheel;
        int[,] pregeneration;
        int[,] nextgeneration;
        

        public Genetic_Algorithm(int populationsize,int chromolength,double c1,double c2,ref double[] value,ref double[] weight1,ref double[] weight2)//initial and set argument
        {

            rand = new Random(System.DateTime.Now.Millisecond);
            MaxTime = 50;

            popsize=populationsize;
            ChromosomeLength = chromolength;
            CrossRate = 0.6;
            MutateRate = 0.1;

            capacity1 = c1;
            capacity2 = c2;
            v = value;
            w1 = weight1; 
            w2 = weight2;

            f = new double[popsize];
            selected = new int[popsize];
            wheel = new double[popsize + 1];
            pregeneration=new int[popsize,ChromosomeLength];
            nextgeneration = new int[popsize, ChromosomeLength];

        }

        public void RunGA()
        {
            int i;
            CreateFirstPop();
            i = 0;
            bool quit = true;
            while (quit)
            {
                for (; i < MaxTime; i++)
                {
                    Console.WriteLine("The {0}th Generation..........", i + 1);
                    CalFitness(ref pregeneration);
                    PrintResult();
                    WheelSelect();
                    CreateNextGeneration();
                    Elitist();
                    Switch(ref pregeneration, ref nextgeneration);
                }
                Console.WriteLine("Press 'q' to quit, press Enter to continue.....");
                if (Console.Read() == 'q')
                {
                    quit = false;
                }
                else
                { 
                    MaxTime += 10; 
                }
            }
        }

        void CreateFirstPop()
        {
            Console.WriteLine("Creating first generation..........\n");
            
            int i,j,r;
            for(i=0;i<popsize;i++)
            {
                
                for(j=0;j<ChromosomeLength;j++)
                {
                    r=rand.Next(2);
                    pregeneration[i, j] = r;
                }
            }
        }

        void CreateNextGeneration()
        {
            int i;
            for (i = 0; i < popsize; i+=2)
            {
                Crossover(selected[i], selected[i + 1], i, i + 1);
            }
            Mutation(ref nextgeneration);
        }

        void CalFitness(ref int[,] curgeneration)
        {

            int i, j;
            double fitness,totalweight1,totalweight2;

            for (i = 0; i < popsize; i++)
            {
                fitness = 0;
                totalweight1 = 0;
                totalweight2 = 0;

                for (j = 0; j < ChromosomeLength; j++)
                {
                    totalweight1 += w1[j] * curgeneration[i, j];
                    totalweight2 += w2[j] * curgeneration[i, j];
                }

                if (totalweight1 <= capacity1 && totalweight2 <= capacity2)
                {
                    for (j = 0; j < ChromosomeLength; j++)
                    {
                        fitness += v[j] * curgeneration[i, j];
                    }
                }

                f[i] = fitness;
            }

        }

        void FindMax(ref double[] f,out int max)
        {
            int i;
            max = 0;
            for (i = 1; i < popsize; i++)
            {
                if (f[i] > f[max])
                {
                    max = i;
                }
            }

        }

        void FindMin(ref double[] f, out int min)
        {
            int i;
            min = 0;
            for (i = 1; i < popsize; i++)
            {
                if (f[i] < f[min])
                {
                    min = i;
                }
            }

        }

        void Elitist()
        {
            int j;
            int max, min;
            CalFitness(ref pregeneration);
            FindMax(ref f, out max);
            CalFitness(ref nextgeneration);
            FindMin(ref f, out min);

            for (j = 0; j < ChromosomeLength; j++)
            {
                nextgeneration[min, j] = pregeneration[max, j];
            }
 
        }

        void WheelSelect() 
        {
            int i,j ,r;
            double sum;

            wheel[0] = 0; sum = 0;
            for (i = 0; i < popsize; i++)
            {
                sum += f[i];
                wheel[i + 1] = wheel[i] + f[i];
            }

            for (i = 0; i < popsize; i++)
            {
                r = rand.Next((int)sum);
                for (j = 0; j < popsize; j++)
                {
                    if (r > wheel[j] && r < wheel[j + 1])
                    {
                        selected[i] = j;
                        break;
                    }
                }
                
            }
        }

        void Crossover(int p1, int p2,int c1,int c2)
        {
            int index1,index2,temp;
            int j;
            double dr = rand.NextDouble();
            if (dr < CrossRate)
            {
                index1 = rand.Next(ChromosomeLength);
                index2 = rand.Next(ChromosomeLength);

                if (index1 > index2)
                {
                    temp = index1;
                    index1 = index2;
                    index2 = temp;
                }
                
                for (j = 0; j < index1; j++)
                {
                    nextgeneration[c1, j] = pregeneration[p1, j];
                    nextgeneration[c2, j] = pregeneration[p2, j];
                }
                for (j = index1; j <= index2; j++)
                {
                    nextgeneration[c1, j] = pregeneration[p2, j];
                    nextgeneration[c2, j] = pregeneration[p1, j];
                }
                for (j = index2+1; j < ChromosomeLength; j++)
                {
                    nextgeneration[c1, j] = pregeneration[p1, j];
                    nextgeneration[c2, j] = pregeneration[p2, j];
                }
            }
            else
            {
                for (j = 0; j < ChromosomeLength; j++)
                {
                    nextgeneration[c1, j] = pregeneration[p1, j];
                    nextgeneration[c2, j] = pregeneration[p2, j];
                }
            }
 
        }

        void Mutation(ref int[,] curgeneration)
        {
            int i,index;
            double dr;

            for (i = 0; i < popsize; i++)
            {
                dr = rand.NextDouble();
                if (dr < MutateRate)
                {
                    index = rand.Next(ChromosomeLength);
                    curgeneration[i, index] = (curgeneration[i, index] + 1) % 2;
                }
            }

        }

        void Switch(ref int[,] g1, ref int[,] g2)
        {
            int[,] temp;
            temp = g1;
            g1 = g2;
            g2 = temp;
        }

        void PrintResult()
        {
            int i,j;
            int max;
            double average;

            average = 0;
            for (i = 0; i < popsize; i++)
            {
                average += f[i];
            }
            average = (int) average / popsize;
            Console.Write("Average profit is {0}\n", average);

            FindMax(ref f, out max);
            Console.Write("Maximum profit is {0} of individual ", f[max]);
            for (j = 0; j < ChromosomeLength; j++)
            {
                Console.Write("{0}", pregeneration[max, j]);
            }
            Console.WriteLine("\n");

        }


    }


    class Program
    {
        static void Main(string[] args)
        {
            //multiple 0/1 Problem
            double capacity1 = 600;
            double capacity2 = 600;
            double[] value ={ 1898, 440, 22507, 270, 14148, 3100, 4650, 30800, 615, 4975, 1160, 4225, 510, 11880, 479, 440, 490, 330, 110, 560, 24355, 2885, 11748, 4550, 750, 3720, 1950, 10500 };
            double[] weight1 ={ 45, 0, 85, 150, 65, 95, 30, 0, 170, 0, 40, 25, 20, 0, 0, 25, 0, 0, 25, 0, 165, 0, 85, 0, 0, 0, 0, 100 };
            double[] weight2 ={ 30, 20, 125, 5, 80, 25, 35, 73, 12, 15, 15, 40, 5, 10, 10, 12, 10, 9, 0, 20, 60, 40, 50, 36, 49, 40, 19, 150 };

            int chromosomelength = 28;
            int populationsize = 2 * chromosomelength;//N=2L;
            Console.WriteLine("Example Of Multi-dimensional 0-1 Knapsack Problem");
            Console.WriteLine("m:2, n:28, 资源一:600, 资源二:600");
            Console.WriteLine("------------------------------------------------------------------------");
            Console.WriteLine("项目    利润  资源一   资源二   ||     项目    利润   资源一   资源二");
            Console.WriteLine("编号          消耗量   消耗量   ||     编号           消耗量   消耗量");
            Console.WriteLine("------------------------------------------------------------------------");
            int i;
            for (i = 0; i < 14; i++)
            {
                Console.WriteLine("{0}\t{1}\t{2}\t{3}\t||\t{4}\t{5}\t{6}\t{7}", i+1, value[i], weight1[i], weight2[i], i + 15, value[i + 14], weight1[i + 14], weight2[i + 14]);
            }
            Console.WriteLine("------------------------------------------------------------------------");
            Console.WriteLine("The max profit to this question is 141278\n");
            Console.WriteLine("Press Enter to start running Genetic Algorithm.");
            Console.ReadKey();

            Genetic_Algorithm GA = new Genetic_Algorithm(populationsize, chromosomelength, capacity1, capacity2, ref value, ref weight1, ref weight2);
            GA.RunGA();

            

        }
    }
}