form1.cs

用C#编写的利用遗传算法解决0-1背包问题的源程序

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using System.IO;

namespace __1背包问题
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }
        string filename;//数据文件名
        int dataNum;//种群大小
        int index;//物品编码
        double TopWeight;//背包总容量
        double PCross;  //杂交概率
        double PVar;    //变异概率
        int MaxGen; //最大代数
        double MaxValue;//最大价值
        double RealWeight;//实际重量
        double[] dataValue;//物品价值
        double[] dataWeight;//物品容量
        bool[,] a;  //选择的个体数据
        private void button1_Click(object sender, EventArgs e)
        {
            if (dataFile.ShowDialog() == DialogResult.OK)
            {
                label2.Text = dataFile.FileName;
                filename = dataFile.FileName;
                if (File.Exists(filename))
                {
                    StreamReader sr = new StreamReader(filename);
                    string tempData = sr.ReadToEnd();
                    sr.Close();
                    //规范化数据
                    tempData = tempData.Replace('\r', ' ');
                    tempData = tempData.Replace('\a', ' ');
                    //以\n分隔背包容量、物品大小和重量
                    string[] s = tempData.Trim().Split('\n');
                    try
                    {
                        //获得背包容量
                        TopWeight = Convert.ToDouble(s[0].Trim());
                        if (s.Length != 3)
                        {
                            MessageBox.Show("数据文件可能格式不对！");
                        }
                        if (s.Length < 3)
                        {
                            MessageBox.Show("数据文件格式不对，无法继续进行!");
                            return;
                        }
                        string[] t_dataValue = s[1].Split(',');
                        string[] t_dataWeight = s[2].Split(',');
                        if (t_dataValue.Length != t_dataWeight.Length)
                        {
                            MessageBox.Show("物品的价值和数量个数不匹配！");
                            return;
                        }
                        dataValue = new double[t_dataValue.Length];
                        dataWeight = new double[t_dataValue.Length];
                        //获得数据
                        for (int i = 0; i < t_dataValue.Length; i++)
                        {
                            dataValue[i] = Convert.ToDouble(t_dataValue[i].Trim());
                            dataWeight[i] = Convert.ToDouble(t_dataWeight[i].Trim());
                        }
                        Run.Enabled = true;
                    }
                    catch
                    {
                        MessageBox.Show("数据文件数据不正确");
                        return;
                    }
                }
                else
                {
                    MessageBox.Show("不能找到文件" + filename);
                    filename = "";
                }
            }
        }

        private void Run_Click(object sender, EventArgs e)
        {
            int K = 0;
            try
            {
                //基本解
                double baseValue = 0.0;
                //如果是寻找更优解，先获取最优解
                if (checkBox1.Checked)
                {
                    baseValue = Convert.ToDouble(textBox3.Text.Trim());
                }
                //初始化最大值
                MaxValue = 0;
                //获得样本大小
                dataNum = Convert.ToInt32(numericUpDown1.Value);
                //获得最小迭代代数
                MaxGen = Convert.ToInt32(numericUpDown2.Value);
                //获得杂交概率
                PCross = Convert.ToDouble(textBox1.Text.ToString().Trim());
                //获得变异概率
                PVar = Convert.ToDouble(textBox2.Text.ToString().Trim());
                //分配最佳编码空间
                index = 0;
                //清空输出框
                richTextBox1.Clear();
                //按照权值从高到低排序
                SortData();
                //设置剩余大小的初始值
                double RestWeight = Double.MaxValue;
                //初始化种群
                GenInitial();
                while (K < MaxGen || RestWeight < TopWeight - RealWeight || MaxValue < baseValue)
                {
                    //选择样本
                    SelectSub();
                    //杂交操作
                    Cross();
                    //变异操作
                    Variation();
                    K++;
                    //计算最小可用物品的空间
                    RestWeight = Double.MaxValue;
                    for (int i = 0; i < dataWeight.Length; i++)
                    {
                        if (!a[index, i] && RestWeight > dataWeight[i])
                            RestWeight = dataWeight[i];
                    }
                }
                richTextBox1.AppendText("携带的物品价值为：" + MaxValue.ToString() + "\n占用空间大小为：" + RealWeight.ToString() + "\n");
                richTextBox1.AppendText("使用的物品序列为：\n");
                for (int i = 0; i < dataValue.Length; i++)
                {
                    if (a[index, i])
                        richTextBox1.AppendText("1 ");
                    else
                        richTextBox1.AppendText("0 ");
                }
            }
            catch
            {
                MessageBox.Show("样本大小、迭代代数、杂交概率和变异概率中有一个数据输入不正确！");
                return;
            }
        }

        private void SortData()
        {
            double[] tempD = new double[dataValue.Length];
            List<int> indexV = new List<int>(dataWeight.Length);
            for (int i = 0; i < tempD.Length; i++)
            {
                tempD[i] = dataValue[i] / dataWeight[i];
                indexV.Insert(i, i);
            }
            for (int i = 1; i < tempD.Length; i++)
            {
                for (int j = 0; j < i; j++)
                {
                    if (tempD[indexV[i]] > tempD[indexV[j]])
                    {
                        indexV.Remove(i);
                        indexV.Insert(j,i);
                    }
                }
            }
            double[] temp1 = new double[dataValue.Length];
            double[] temp2 = new double[dataValue.Length];
            for (int i=0;i<temp1.Length;i++)
            {
                temp1[i] = dataValue[indexV[i]];
                temp2[i] = dataWeight[indexV[i]];
            }
            for (int i = 0; i < temp1.Length; i++)
            {
                dataValue[i] = temp1[i];
                dataWeight[i] = temp2[i];
            }
            richTextBox1.AppendText("背包总大小为：" + TopWeight.ToString() + "\n");
            richTextBox1.AppendText("物品的价值(大小)为：\n");
            for (int i = 0; i < dataValue.Length; i++)
            {
                richTextBox1.AppendText(dataValue[i].ToString() + "("+dataWeight[i].ToString()+")\t");
            }
            richTextBox1.AppendText("\n");
        }

        private void Variation()
        {
            Random x = new Random();
            Random y = new Random();
            for (int i = 0; i < dataNum; i++)
            {
                for (int j = 0; j < dataValue.Length; j++)
                {
                    double randomNum = Math.Sqrt(-2 * Math.Log(x.NextDouble())) * Math.Cos(2 * Math.PI * y.NextDouble());
                    //当大于变异概率时，则对该位进行变异操作
                    if (randomNum > 1 - PVar)
                    {
                        a[i, j] = !a[i, j];
                    }
                }
            }
            //修正数据
            ModifyData();
        }

        private void Cross()
        {
            Random x = new Random();
            for (int i = 0; i < dataNum; i += 2)
            {
                if (x.NextDouble() > 1-PCross)//当大于杂交概率时，两个样本进行杂交
                {
                    //依次遍历每一位，根据均匀概率随机生成杂交掩码进行杂交
                    for (int j = 0; j < dataValue.Length; j++)
                    {
                        if (x.NextDouble() > 0.5)//i与i+1的第j位进行杂交
                        {
                            if (a[i, j] != a[i + 1, j])
                            {
                                a[i, j] = !a[i, j];
                                a[i + 1, j] = !a[i + 1, j];
                            }
                        }
                    }
                }
            }
            //修正数据
            ModifyData();
        }

        private void SelectSub()//选择操作
        {
            double[] elv = new double[dataNum];
            //确保这一代中的最好个体进入下一代
            CopyParent(index, 0);
            //计算这一代中各个体的适应值
            for (int i = 0; i < dataNum; i++)
            {
                if (i == 0)
                    elv[i] = 0;
                else
                    elv[i] = elv[i - 1];
                for (int j = 0; j < dataValue.Length; j++)
                {
                    if(a[i,j])
                        elv[i] += dataValue[j];
                }
            }
            //选择下一代种群
            Random x = new Random();
            double c;
            for (int j = 1; j < dataNum; j++)
            {
                c = x.NextDouble()*elv[dataNum-1];
                for (int i = 0; i < dataNum; i++)
                {
                    if (c < elv[i])
                    {
                        CopyParent(i, j);
                        break;
                    }
                }
            }
        }
        private void CopyParent(int from, int to)
        {
            for (int i = 0; i < dataValue.Length; i++)
            {
                a[to, i] = a[from, i];
            }
        }
        private void ModifyData()
        {
            double tempW;
            double tempV;
            MaxValue = 0;
            for (int i = 0; i < dataNum; i++)
            {
                tempW = 0;
                tempV = 0;
                for (int j = 0; j < dataValue.Length; j++)
                {
                    if (a[i, j])
                    {
                        if (tempW + dataWeight[j] > TopWeight)
                            a[i, j] = false;
                        else
                        {
                            tempW += dataWeight[j];
                            tempV += dataValue[j];
                        }
                    }
                }
                if (tempV > MaxValue)
                {
                    index = i;
                    MaxValue = tempV;
                    RealWeight = tempW;
                }
            }
        }

        private void GenInitial()
        {
            Random x = new Random();
            a = new bool[dataNum, dataValue.Length];
            /////////随机生成一个样本容量//////////////////////////////
            for (int j = 0; j < dataNum; j++)
            {
                for (int i = 0; i < dataValue.Length; i++)
                {
                    if (x.NextDouble() > 0.5)
                    {
                        a[j, i] = true;
                    }
                    else
                        a[j, i] = false;
                }
            }
            //////////////修正数据，使得数据落在可行解的范围内/////////////////
            ModifyData();
        }

        private void checkBox1_CheckedChanged(object sender, EventArgs e)
        {
            if (checkBox1.Checked)
            {
                textBox3.Enabled = true;
            }
            else
            {
                textBox3.Enabled = false;
            }
        }
    }
}