advancedsearch.txt

高级搜索算法

1．搜索方式，解图(树)   
          同状态图(即或图)的搜索一样，与或图搜索也分为树式和“线”式两种类型。对于树式   
  搜索来讲，其搜索过程也是不断地扩展节点，并配以返回指针，而形成一棵不断生长酌搜   
  素材。但与或图搜：夷解图(树)，不像在或图中那样只是简单地寻找目标节点，而是边扩展   
  节点边进行逻辑判断，以确定初始节点是否可解。一旦能够确定初始节点的可解性，则搜   
  索停止。这时，根据返回指针便可从搜索树中得到一个解图(树)。所以，准确地说，解图   
  (树)实际上是由可解节点形成的一个子图(树)，这个子图(树)的根为初始节点，叶为终止   
  节点，且这个子图(树)还—定是与图(树)。   
              (2)一个节点是不可解，则节点须满足下列条件之一：         ①非终止节点的端节点是不可解节点；         ②一个与节点不可解，只要其子节点至少有一个不可解；         ②一个或节点不可解，当且仅当其子节点全都不可解。         3．搜索策略         与或图搜索也分为盲目搜索和启发式搜索两大类。前者又分为穷举搜索和盲目碰撞搜索。穷举搜索又分为深度优先和广度优先两种基本策略。         4．搜索算法         同一般状态图搜索一样，一般与或图搜索也涉及一些复杂的处理。因篇幅所限，我们仅介绍待殊的与或因——与或树的搜索算法。与或树的树式搜索过程可概括为以下步骤：步1     把初始节点犀。放入OPEN表；步2     移出OPEN表的第一个节点N放入CLOSEDD表，并冠以序号M步3     若节点付可扩展，则做下列工作：(1)扩展N，将其子节点配上指向父节点的指针后放入OPEN表；         (2)考察这些子节点中是否有终止节点。若有，则标记它们为可解节点，并将它们也故入CLOSED表，然后由它们酌可解返回推断其先辈节点的可解性，并对其中的可解节点进行标记。如果韧始节点也被标记为可解节点，则搜索成功，结束。         (3)删去OPEN表中那些具有可解先辈的节点(因为其先辈节点已经可解考察节点的必要)，转步2；         步4     若付不可扩展，则做下列工作：         (1)标记付为不可解节点，然后由它的不可解返回推断其先辈节点的可解性．并对其中的不可解节点进行标记。如果初始节点S0也被标记为不可解节点，则搜索失败，退出。         (2)删去OPEN表中那些具有不可解先辈的节点(因为其先辈节点已不可解，故已无再考察这些节点的必要)，转步2；   
          同状态图搜索一样，搜索成功后，解树已经记录在CLOSED表中。   
  点的指针找出整个解树。下面举一个广度优先搜索的例子。   
  4．3．3     启发式与或树搜索         广度优先搜索及深度优先搜索都是盲目搜索，其共同点是：         (1)搜索从初始节点开始．先自上而下地进行搜索，寻找终止节点及端节点，然后再自下而上地进行可解性标记，一旦初始节点被标记为可解节点或不可解节点，搜索就不再继续进行。         (2)搜索都是按确定路线进行的，当要选择一个节点进行扩展时或树中所处的位置，而没有考虑要付出的代价，因而求得的解树不—树，即不一定是最优照例。只是根据节点在与定是代价最小的解         为了求得最优解树，就要在每次确定欲扩展的节点时，先往前多看几步，计算一下扩展这个节点可能要付出的代价，并选择代价最小的节点进行扩展。像这样根据代价决定理索路线的方法称为与或树的有序搜索，它是一种重要的启发式搜索策略。         下面分别讨论与或树有序搜索的有关慨念及其搜索过程。         1．解树的代价         解树的代价就是树根的代价。树根的代价是从树叶开始自下而上逐层计算而求得的而解树的根对应的是初姑节点S0.这就是说，在与或材的搜索过程中，代价的计算方向与搜索树的生长方向相反。这一点是与状态图不同的。具体来讲，有下面的计算方法：         设g(x)表示节点f的代价，c(x，y)表示节点x到其子节点y的代价(即xy的代价)，则         (1)若x是终止节点，g(x)＝0；         (z)若x是或节点，g(x)＝min{c(x，y)+g(yi)}其中y1，y2，…yn是x的子节点；         (3)若x是与节点x，则有两种计算公式         ①g(x)＝z{c(x，yi)+g(yi)}称为和代价法，         ②g(z)＝max{(c(x，yi)-g(yi)}称为最大代价法，其中y1，y2，…，yq是f的子节点         (4)对非终止的端节点x，g(x)＝max   2．希望树         无论是用和代价法还是最大代价法，当要计算任一节点x的代价g(x)时，都要求已知其子节点从的代价g(yi)。但是，搜索是白上而下进行的，即先有父节点．后有于节与．除非节点c的全部子节点部是不可扩展节点．否则子节点的代价是不知道的。此时节点f的代价g(x)如何计算呢?解决的办法是根据问题本身提供的启发性信息定义一个启发函数，   
            由启发函数估算出子节点yi的代价g(yi)，然后再按和代价或最大代价算出节点x的代价   
  值g(x)。有了g(x)，节点x的父节点、祖父节点以及直到初始节点s0的各先辈节点的代   
  价g都可自下而上的地逐层推算出来。   
          当节点yi被扩展后，也是先用启发函数估算出其子节点的代价，然后再算出g(y)。   
  此时算出的g(yi)可能与原先估算出的g(yi)不相同，这时应该用后算出的g(yi)取代原先   
  估算出的g(yi)，并且按此g(yi)自下而上地重新计算各先辈节点的g值。当节点yi的子节   
  点又被扩展时，．L：述过程又要重复进行一遏。总之，每当有新一代的节点生成时，都要自   
  下而上地重新计算其先辈节点的代价g,这是一个自上而下地生成新节点，又自下而上地   
  计算代价g的反复进行的过程。   
          有序搜索的日的是求出最优解树，即代价最小的解材。这就要求按索过程中任一时刻   
  求出的部分解树其代价都应是最小的。为此，每次选择欲扩展的节点时都应挑选有希望成   
  为最优解树一部分的节点进行扩展。(1)初始节点s0在希望树T中。   
  (2)如果节点x在希望树T中，则一定有：   
  ①如果x是具有子节点y1，y2，…，yn的“或”节点   
  min{c(x,yi)+g(yi)}(1<＝i<=n)   
  值的那个子节点yi也应在T中。   
          ⑨如果2是“与”节点，则它的全部子节点都应在丁中   
          3．与或树的有序搜索过程   
          与或树的有序搜索过程是一个不断选择、修正希望树的过程   
  序搜索将找到员优解树。   
      其搜索过程如下：   
      (1)把初姑节点s0放入OPEN表中。   
  (2)求出希望树了，即根据当前搜索树中节点的代价S0求出以置。为根的希望树7。   
  (3)依次把OPEN表中T的端节点N选出放入CLOSED表中。   
  (4)如果节点N是终止节点，则做下列工作：   
      ①标示N为可解节点。   
      ②对T应用可解标记过程，把N的先辈节点中的可解节点都标记为可解节点   
      ②若初始节点s0能被标记为可解节点，则T就是最优解树，成功退出。   
      ④否则，从OPEN表中删去具有可解先辈的所有节点。   
  (5)如果节点N不是终止节点，且它不可扩展，则做下列工作：   
      ①标示N为不可解节点。   
      ②对T应用不不可解标记过程，把N的先辈节点中的不可解节点都标记为不可解节点     ③若初始节点s0。也被标记为不可解节点，则失败退出。   
      ＠否则，从OPEN表中删去具有不可解先辈的的所有节点   
  (6)如果节点AP不是终止节点，但它可扩展，则可做下列工作：   
          ①扩展节点N，产生N的所有子节点。   
          ②把这些子节点都放入OPEN表中，并为每—子节点配置指针。   
          ②计算这些子节点的f值及其先辈节点的g值   
  (7)转(2)。   


遗传算法(Genetic   Algorithm,GA)是一种抽象于生物进化过程的基于自然选择和生物遗传机制的优化技术.       
  遗传算法的基本原理         
  在遗传算法的执行过程中,每一代有许多不同的种群个体(染色体   )同时存在。这些染色体中哪个保留(生存)、哪个淘汰(死亡),是根据   它们对环境的适应能力来决定的,适应性强的有更多的机会保留下来   。适应性强弱是通过计算适应性函数f(x)的值来判别的,这个值称为适应值。适应值函数f(x)的构成与目标函数有密切关系,往往是目标函数的变种。主要的遗传算子有如下几种:       
  1.选择(Selection)算子又称复制(reproduction)、繁殖算子。选择是从种群中选择生命力强的染色体,产生新种群的过程。选择的依据是每个染色体的适应值大小,适应值越大,被选中的概率就越大,其子孙在下一代产生的个数就越多。选择的方法根据不同的问题,采用不同的方案。最常见的方法有比率法、排列法和比率排列法。         
  2.交叉(Crossover)算子又称重组(recombination)、配对(breeding)算子。当许多染色体相同或后代的染色体与上一代没有多大差别时,可通过染色体重组来产生新一代染色体。染色体重组分两个步骤进行:首先,在新复制的群体中随机选取两个染色体,每个染色体由多个位(基因)组成;然后,沿着这两个染色体的基因随机取一个位置,二者互换从该位置起的末尾部分基因。例如,有两个用二进制编码的个体A和B,长度L=5,A=a1a2a3a4a5,B=b1b2b3b4b5。随机选择一个整数k∈[1,L-1],设k=4,经交叉后变为:         
  A=a1a2a3|a4a5       A'=a1a2a3b4b5         
  B=b1b2b3|b4b5       B'=b1b2b3a4a5         
  遗传算法的有效性主要来自选择和交叉操作,尤其是交叉,在遗传算法中起着核心作用。         
  3.变异(Mutation)算子         
  选择和交叉算子基本上完成了遗传算法的大部分搜索功能,而变异则增加了遗传算法找到接近最优解的能力。变异就是以很小的概率,随机改变字符串某个位置上的值。在二进制编码中,就是将0变成1,将1变成0。变异发生的概率极低(一般取值在0.001～0.02之间)。它本身是一种随机搜索,但与选择、交叉算子结合在一起,就能避免由复制和交叉算子引起的某些信息的永久性丢失,从而保证了遗传算法的有效性。         
  传算法是多学科结合与渗透的产物,已经发展成一种自组织、自适应的综合技术,广泛应用在计算机科学、工程技术和社会科学等领域。其研究工作主要集中在以下几个方面         
  1.基础理论         
  包括进一步发展遗传算法的数学基础,从理论和试验研究它们的计算复杂性。在遗传算法中,群体规模和遗传算子的控制参数的选取非常困难,但它们又是必不可少的试验参数。在这方面,已有一些具有指导性的试验结果。遗传算法还有一个过早收敛的问题,怎样阻止过早收敛也是人们正在研究的问题之一。         
  2.分布并行遗传算法         
  遗传算法在操作上具有高度的并行性,许多研究人员都在探索在并行机和分布式系统上高效执行遗传算法的策略。对分布并行遗传算法的研究表明,只要通过保持多个群体和恰当控制群体间的相互作用来模拟并行执行过程,即使不使用并行计算机,也能提高算法的执行效率。         
  3.分类系统         
  分类系统属于基于遗传算法的机器学习中的一类,包括一个简单的基于串规则的并行生成子系统、规则评价子系统和遗传算法子系统。分类系统被人们越来越多地应用在科学、工程和经济领域中,是目前遗传算法研究中一个十分活跃的领域。         
  4.遗传神经网络         
  包括连接权、网络结构和学习规则的进化。遗传算法与神经网络相结合,正成功地用于从时间序列分析来进行财政预算。在这些系统中,训练信号是模糊的,数据是有噪声的,一般很难正确给出每个执行的定量评价。如果采用遗传算法来学习,就能克服这些困难,显著提高系统性能。Muhlenbein分析了多层感知机网络的局限性,并猜想下一代神经网络将是遗传神经网络。         
  5.进化算法         
  模拟自然进化过程可以产生鲁棒的计算机算法——进化算法。遗传算法是其三种典型的算法之一,其余两种算法是进化规划(Evolutionary   Programming,EP)和进化策略(Evolutio   nary   Strategies,ES)。这三种算法是彼此独立地发展起来的。进化规划最早由美国的L.J.Fogel、A.J.Owens和M.J.Walsh提出;进化策略则由德国的I.Rechenberg和H.P.Schwefel建立。具体应用也很广，我就拿它解决了好几个难题。       
  下面我给出我们校数学建模时的程序你分析一下就明白了。       
  #define   Ins   35   /*指令数*/       
  #define   Com   45/*部件数*/       
  #define   Row   100       
  #define   JCn   0*Row/*交叉的概率*/       
  #define   FZn   .15*Row       
  #define   PY     Row-JCn-FZn       
  #define   times       1000   /*迭代次数*/       
  #define   hyR           .4*Ins/*交叉概率*/       
  #define   Optnum     5   /*最优解的个数*/       
  #include   "stdlib.h"       
  #include   "time.h"       
  #include   "stdio.h"       
  #include   "conio.h"       
  unsigned   char   *A[Row+1];           /*遗传矩阵*/       
  unsigned   char   *Aimg[Row+1];     /*A的备份*/       
  unsigned   long   Aused[Row+1];       
  unsigned   long   Acomnum[Row+1];       
  unsigned   long   Ainsnum[Row+1];       
  unsigned   long   Opt[Optnum+1][Ins+1];                   /*最优的解*/       
  unsigned   long   Optins[Optnum+1];             /*最优解的指令个数*/       
  double   ada[Ins+1];                       /*行适应度*/       
  char   ins[Ins+1][Com+1]={{0},{0,4,8,20,31,44},{0,8,19,22,29,37}，{0,2,16,34,33,32},{0,7,11,35,30},{0,5,13,18,21},{0,1,7,9,23,25},       
  {0,3,5,6,14,24},{0,7,20,21,32,35},{0,9,15,20,45},{0,6,10,39,42,43},{0,1,11,21,34,38},{0,2,4,18,22,37},{0,6,17,25,36},{0,22,33,34,38},{0,2,10,20,37},{0,9,24,29,39},{0,15,18,29,31},{0,4,42,44,45},{0,13,23,26,39},{0,7,12,40,41},{0,12,16,19,28,35},{0,6,23,27,45},{0,33,37,40,41},{0,3,17,19,36},{0,16,33,44,45},{0,13,19,24,25},{0,2,3,5,8},{0,4,7,9,12,43},{0,16,17,20,32},{0,28,33,34,36},{0,10,23,25,27},{0,1,5,44,45},{0,11,15,18,43},{0,7,14,22,36},{0,3,15,25,39}};/*促使*/       
  char   inslen[Ins+1]={0,15,80,30,12,7,19,32,12,45,36,57,78,65,53,34,48,46,32,26,22,26,19,17,22,10,30,82,73,66,55,24,46,37,77,9};/*指令长度*/       
  unsigned   long   step=0;       
  void   iniA(void);           /*初始化A*/       
  void   adaRate(void);     /*适应度*/       
  void   judge(void);         /*判断*/       
  void   elim(void);           /*选取:最优的五个解*/       
  void   JC(void);               /*交叉*/       
  void   FZ1(void);             /*复制*/       
  void   PY1(void);             /*变异*/       
  void   back(void);       
  void   showA(void);           /*给出A*/       
  void   showOpt(void);       /*给出最优解*/       
  double   rnd(void);         /*给出0~1间的随机数*/       
  void   main(void)       
  {randomize();       
  iniA();       
  while(1)       
  {adaRate();       
  judge();       
  elim();       
  if(step++>=times)       
    break;       
    JC();       
  FZ1();       
  PY1();       
  back();       
  }       
  showOpt();       
  }       
  void   iniA(void)       
  {unsigned   long   i,j,knum=0;       
  for(i=1;i<=Row;i++)     
  A[i]=(unsigned   char   *)malloc(sizeof(char)*(Ins+1));     
  Aimg[i]=(unsigned   char   *)malloc(sizeof(char)*(Ins+1));     
  }     
  for(i=1;i<=Row;i++)     
  {for(j=1;j<=Ins;j++)     
  {if(rnd()>0.5)   A[i][j]=1;       
  else   a[i][j]=0;       
    }                 
  }       
  for(i=1;i<=Optnum;i++)     
  {for(j=1;j<=Ins;j++)     
  {Opt[i][j]=1;     
  Optins[i]+=inslen[j];     
  }     
  }     
  }     
  void   adaRate(void)     
  {unsigned   long   i,j,k;     
  double   insnum,comnum;     
  int   iscom[Com+1];   /**   部件是否出现   **/     
  for(i=1;i<=Row;i++)     
  {ada[i]=insnum=comnum=0;     
  for(j=1;j<=Com;j++)     
  iscom[j]=0;     
  for(j=1;j<=Ins;j++)     
  if(A[i][j])     
  {insnum+=inslen[j];     
  for(k=1;k<=Com;k++)     
  iscom[ins[j][k]]=1;     
  }     
  for(j=1;j<=Com;j++)     
  if(iscom[j])   comnum+=1;     
  if(insnum)     
  ada[i]=comnum/insnum;   /**适应度函数**/     
  else     
  ada[i]=0;     
  Acomnum[i]=comnum;     
  Ainsnum[i]=insnum;     
  }}     
  void   judge(void)     
  {}     
  void   elim(void)     
  {unsigned   long   i,j,k;     
  for(i=1;i<=Row;i++)   /*检查是否有更优解*/     
  if(Acomnum[i]==Com)     
  {for(j=1;j<=Optnum;j++)