遺傳算法的簡單應用-求解方程

上篇初識遺傳算法講述了遺傳算法的基本思想，這篇部落格就用遺傳算法求解方程。

具體的如下：

求解方程 -x^3+7*x+13=0 在[3,4]區間的解，解精确到0.001，交叉機率0.7

變異機率0.01，疊代次數為100，字元編碼長度為10(二進制編碼)

首先簡單的分析一下：

1、編碼與解碼

題目要求的是采用二進制的編碼方式來實作，既然已經編碼了，自然就需要解碼，給定的10

位二進制編碼表示的區間範圍就是0~1023，題目的區間是[3,4]很自然的就能想到10位二進

制編碼中的0表示是就是[3,4]中的3，1023表示的就是[3,4]中的4，是以，每個二進制對應的

十進制就是((10位二進制對應的十進制數/1023)+3)，這個就是解碼後的在區間[3,4]中的具體值。

2、适應度函數

 這裡取的适應度函數是方程絕對值的倒數，即f=1/(|-x^3+7*x+13|)

3、選擇算子

确定選擇比例，采用輪盤賭算法。

/// <summary>
        /// 模拟輪盤賭選擇算法
        /// 思路：1.求适應度的總和;2.計算每個個體适應度所占的比例(除第一個之外，其他的都是疊加);
        /// 3.在0~1産生随機數，這個随機數所在的區間，就是要選擇的個體
        /// </summary>
        /// <returns>選擇出來的優秀個體</returns>
        static List<int> RWS(List<double> list)
        {
            List<int> select = new List<int>();
            List<double> p = new List<double>();
            double sum = list.Sum()/*适應度之和*/, temp = 0/*臨時變量*/;
            foreach (var item in list)
            {
                temp += (item / sum);//疊加
                p.Add(temp);//機率
            }
            int i, j;
            for (i = 0; i < p.Count; i++)
            {
                temp = rd.NextDouble();//0~1的随機數
                for (j = 0; j < p.Count; j++)
                {
                    if (j == 0 && temp < p[0])
                    {
                        select.Add(0);
                    }
                    else if (temp < p[j] && temp >= p[j - 1])
                    {
                        select.Add(j);
                    }
                }
            }           
            return select;
        }      

View Code

4、交配算子

随機産生交配位，交換兩個染色體的部分基因。

/// <summary>
        /// 交叉過程個體的變化(字元的替換)
        /// </summary>
        /// <param name="dic">參加交叉的兩個個體</param>
        /// <param name="geti1">個體1</param>
        /// <param name="geti2">個體2</param>
        /// <returns></returns>
        static List<string> Crossover_Replace(Dictionary<int, int> dic, string geti1, string geti2)
        {
            int index; double p;
            List<string> tmp_group = new List<string>();//存放交叉過後的個體
            foreach (var item in dic)
            {
                p = rd.NextDouble();
                if (p <= crossover_probability)//機率小于0.7進行交叉
                {
                    index = rd.Next(0, 8);
                    geti1 = group[item.Key];//要交叉的兩個個體
                    geti2 = group[item.Value];
                    //交叉的實作
                    tmp_group.Add(geti1.Insert(geti1.Length, geti2.Substring(index)).Remove(index, str_length - index));
                    tmp_group.Add(geti2.Insert(geti2.Length, geti1.Substring(index)).Remove(index, str_length - index));
                }
                else
                {
                    tmp_group.Add(group[item.Key]);
                    tmp_group.Add(group[item.Value]);
                }
            }
            return tmp_group;
        }      

5、變異算子

變換染色體基因的值，即0-1，1-0的變換。

/// <summary>
        /// 變異過程個體的變化(0->1,1->0)
        /// 思路:1.将個體的編碼轉化成字元;2.為每個字元産生一個0~1的随機數,判斷是否要進行變異操作
        /// 3.要變異則将0->1,1->0
        /// </summary>
        /// <param name="str">個體(二進制編碼)</param>
        /// <param name="result">變異後的結果</param>
        /// <param name="probability">變異機率</param>
        /// <returns></returns>
        static string Mutation_Replace(string str, string result, double probability)
        {
            char[] chrArray = str.ToCharArray();
            for (int i = 0; i < chrArray.Count(); i++)
            {
                //小于機率,替換字元
                if (rd.NextDouble() <= probability)
                {
                    if (chrArray[i] == '0')
                    {
                        chrArray[i] = '1';
                    }
                    else if (chrArray[i] == '1')
                    {
                        chrArray[i] = '0';
                    }
                }
            }
            //将字元拼接成字元串
            foreach (char ch in chrArray)
            {
                result += ch;
            }
            return result;
        }      

其中的方法，實作不唯一，時間比較敢，也沒有作一定的優化，隻是為了熟悉算法而寫的。