黑马程序员技术交流社区

标题: 抽样找最小路径 [打印本页]
作者: sunrise2    时间: 2014-8-12 14:56
标题: 抽样找最小路径
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;

  6.     class Gens
  7.     {
  8.         private static List<List<int>> Populations = new List<List<int>>(0);

  10.         private static List<Children> TargetGenePool = new List<Children>(0);

  12.         private static int GenLength = 8;

  14.         private static int MaxPopSize = 1000;

  16.         private static Random rdm = new Random(1);

  18.         private static int[] Data = new int[] {1,2,3,4,5,6,7,8,9};

  20.         private static string BestChromsome = string.Empty;

  22.         static void Main()
  23.         {
  24.             InitialPop();
  25.             EvaluateFitness(Populations);
  26.             
  27.            TargetGenePool = TargetGenePool.Distinct().ToList();
  28.            EvaluateDistance(TargetGenePool);
  29.            int value = TargetGenePool.Min(a=>a.DistanceOffSet);
  30.            List<Children> TempValue =  TargetGenePool.FindAll(a=>a.DistanceOffSet==value);
  31.             foreach (var Item in TempValue)
  32.             {
  33.                 StringBuilder sb =new StringBuilder();
  34.                 foreach (var unite in Item.Chromsome)
  35.                 {
  36.                     sb.Append(unite);
  37.                 }
  38.                 if (BestChromsome != sb.ToString())
  39.                 {
  40.                     BestChromsome = sb.ToString();
  41.                     System.Diagnostics.Trace.WriteLine("最佳基因:" + BestChromsome);
  42.                 }
  43.                
  44.             }
  45.             
  46.         }

  48.         static void EvaluateDistance(List<Children> ChromsomeList)
  49.         {
  50.             foreach(var chromsome in ChromsomeList)
  51.             {
  52.                 List<int> values = new List<int>(0);
  53.                 for (int Index = 0; Index < chromsome.Chromsome.Count;Index++)
  54.                 {
  55.                     if(chromsome.Chromsome[Index]!=0)
  56.                     {
  57.                         values.Add(Data[Index]);
  58.                     }
  59.                 }

  61.                 int distance = 0;
  62.                 for (int i = values.Count-1; i >0; i--)
  63.                 {

  65.                     if(i-1>=0)
  66.                     {
  67.                         distance += (values[i] - values[i - 1]);
  68.                     }
  69.                      
  70.                 }
  71.                 chromsome.DistanceOffSet = distance;
  72.             }
  73.          
  74.          
  75.         }

  77.         static void EvaluateFitness(List<List<int>> Pop)
  78.         {
  79.             foreach (var ItemCollection in Pop)
  80.             {
  81.                 double fitness = 0.0;
  82.                 double Sum = 0;
  83.                 for (int Index = 0; Index < ItemCollection.Count;Index++)
  84.                 {
  85.                     if (ItemCollection[Index] != 0)
  86.                     {
  87.                         double Value = Data[Index];
  88.                         Sum += Value;
  89.                     }
  90.                 }
  91.                  
  92.                 if (Sum == 10)
  93.                 {
  94.                     fitness = 1.0;
  95.                     Children child = new Children();
  96.                     child.Fitness = fitness;
  97.                     child.Chromsome = ItemCollection;
  98.                     TargetGenePool.Add(child);
  99.                 }
  100.                  
  101.             }
  102.         }

  104.         static void InitialPop()
  105.         {
  106.             int PopSize = 0;
  107.             while (PopSize < MaxPopSize)
  108.             {
  109.                 List<int> gen = new List<int>(0);
  110.                 int currentlength = 0;
  111.                 while (currentlength <= GenLength)
  112.                 {
  113.                     gen.Add(CreateUnite());
  114.                     currentlength++;
  115.                 }
  116.                 Populations.Add(gen);
  117.                 PopSize++;
  118.             }
  119.         }

  121.         static int CreateUnite()
  122.         {
  123.             return rdm.Next(0,2);
  124.         }

  126.     }

  128.    
  129.     class Children
  130.     {
  131.         /// <summary>
  132.         /// 基因序列
  133.         /// </summary>
  134.         private List<int> chromsome= new List<int>(0);
  135.         public List<int> Chromsome
  136.         {
  137.             get
  138.             {
  139.                 return chromsome;
  140.             }
  141.             set
  142.             {
  143.                 chromsome = value;
  144.             }
  145.         }

  147.         

  149.         /// <summary>
  150.         /// 适应度
  151.         /// </summary>
  152.         private double fitness;
  153.         public double Fitness
  154.         {
  155.             get
  156.             {
  157.                 return fitness;
  158.             }
  159.             set
  160.             {
  161.                 fitness = value;
  162.             }
  163.         }

  165.         /// <summary>
  166.         /// 路径差
  167.         /// </summary>
  168.         private int distanceoffset;
  169.         public int DistanceOffSet
  170.         {
  171.             get
  172.             {
  173.                 return distanceoffset;
  174.             }
  175.             set
  176.             {
  177.                 distanceoffset = value;
  178.             }
  179.          
  180.         }
  181.      
  182.     }
复制代码






欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2