- 发帖可能变空内容，邪门暂不知所以然
- 『稷下学宫』新认证方式，24年网站打算和努力目标
主题：【原创】和风满袖兄一篇：谈谈遗传规划 -- 好兵帅克
以达尔文进化思想为基础发展起来的一系列算法技术统称为进化算法（EA，evolutionary algorithms），包括遗传算法，进化策略，进化规划，遗传规划等，其中最典型和应用最广泛的是遗传算法。进化算法的基本原理是选择和改变，它区别于其他搜索（优化）方法有两个显著特征：首先这些算法都是基于种群（population）的；其次在种群中个体（individual）之间存在竞争。
进化计算的一般优点在于：1.采用编码技术表示对象（就是所求解的问题啦）的结构，对对象的数学描述形式要求不严格（连续、可微、单峰等），能够很方便用计算机程序实现；2.基于生物进化理论和自然选择策略实现自组织优化过程；3.通过种群搜索实现多区域并行进化，寻优效率高。
兄弟我感兴趣的是遗传规划（genetic programming）。自计算机出现以来，计算机科学的一个重要目标就是让计算机自动进行程序设计，即只要明确地告诉计算机要解决的问题，而不需要告诉它如何去做，遗传规划（Genetic Programming，GP）或者称为遗传编程就是在这一领域的尝试。遗传规划不象GA中将问题解编码成固定长度的二进制或十进制字符串，而是使用一种更为灵活的方式――分层结构来表示解空间，这些分层结构的叶节点是问题的原始变量，中间节点则是组合这些原始变量的函数。这样，GP就克服了在表示方式上的局限，能够对群体中独立的程序个体进行操作，自动生成解决问题的程序。
相对于GA，GP采用的是一种更为自然的表示方式，因此是一种应用领域更为广泛的遗传或进化搜索技术。日本ATR研究中心的H.de Garis甚至提出GP不仅可以演化计算机程序，而且可以演化任何复杂系统，直至人的大脑这么复杂的东东。
在经典的遗传规划中，染色体个体为包含函数集和终止符集的层次结构，其中函数集包括运算符号、数学函数、条件表达式等等，终止符集包括变量（如描述系统的输入、状态变量）、常数、无参函数等等。函数集和终止符集也可以是您自己针对问题定义的关系式和运算符，反正定义这些的目的就是要把研究的对象描述清楚。那怎么就算是描述清楚了呢？也就是说，函数集与终止符集的构造必须满足Koza所说的闭合性和充分性。闭合性确保GP中产生语法上正确的个体，即根据设定算子产生出来的个体对这个问题来说都必须是一个有意义的解。充分性就是说，问题的所有有意义的解都应该可以用所提供的终止符与函数的组和完全表示出来。
应用遗传规划解决问题时，应首先确定：①函数集；②终止符集；③适应度；④控制运行的参数（及变量）；⑤表明结果的方法和终止运行的准则。
（这段不感兴趣可以不看。）
在经典的GP算法中，初始群体（第0代）中的个体是随机生成的由给定的函数和终止符构成的程序组合，生长过程中可以限定树型结构叶节点的深度，当所有子节点为终止符时生长停止。遗传编程的基本操作包括复制、交叉、变异等。其中，复制操作即基于适应度随机地选择1个个体，将其拷贝到下一代群体中，个体的适应度越大，它被选中的概率越大。而交叉操作是从2个随机选取的父代个体中产生2个子代个体，2个交叉点分别在父代个体中随机选取。突变操作是随机选中父代个体上的突变点，该结点处的子树就被删除，而后应用类似于生成初始个体的生长方法生成新的子树。经过群体进化，最终确定一个个体程序作为遗传规划的运行结果。遗传规划传统上依照遗传算法思想设计遗传算子，用非定长层次结构反映求解问题的特征。
使用GP算法解决优化问题必须也只须具备两个前提：
1.该问题可以确定地判定解的优劣，即能够给出适应度准则；
2.问题的解必须能够能成功地用函数集与终止符集表示。
再拿GA和GP比较一下。如果GP的树状个体简化成为不分叉的一条链，链中所有的元素都是一位数，然后把链的长度固定下来，这就是GA中的染色体结构。可见，与GA的数值自组织优化过程相比，GP算法是一个更灵活的变结构自组织优化过程，问题的可行解是由遗传操作算子通过动态地改变个体结构和数值而获得的。这是多么flexible的一个东东啊。
在算法领域，GP的理想状态是，假如你给定一个计算目标，然后提供一堆足够的子程序、函数、过程什么的，它能够自己给你组合起来形成一个完整的程序实现这个目标，还是结构非常完美的一个程序。在路径规划这类问题上，已经有很多应用的结果了。也有很多paper把它叫做遗传编程的。一般的，我觉得在软件科学领域把它叫做遗传编程的比较多；在优化计算领域把它叫做遗传规划的比较多。我觉得叫遗传规划比较好听，而且听起来跟其它EA的关系比较密切一点。
可是它就那么好吗？那为什么大家都不怎么用呢？对于搜索问题来说，flexibility和complexity总是矛盾的。在GP应用过程中，如果函数集和终止符集的元素较多，搜索空间呈现组合膨胀，搜索时间过长，不能得到理想的结果。因此现在GP算法的收敛速度还是个大问题，不过这个问题归根到底还是可以在发展过程中解决的嘛，没见cpu越来越快，内存越来越大了吗？
就喜欢这样的文章，扫偶对科学的盲呀
老大还有东东吗？多多益善呀。
对了，不知道老大对蚁群优化（不知道该怎么确切翻译，只依稀记的好象是根据群体动物的迁徙特性而引申出的优化算法，似乎就想一大群蚂蚁要搬家，忽忽悠悠的一大群，但总能比较正确的完成任务
）有了解吗？
源于self-adaptive system和intelligent agent,以蚁群为例,单个蚂蚁的行动很简单而且也很容易模拟,但是整个蚁群却可以实现很多复杂的事情.在解决某些复杂问题时,不能够马上得到一个完整的解,那么是否可以只先解决一些问题的片断,得到一个部分的不完整的解题程序,然后只增加这些小程序的数量来得到一个还算满意的全局解.比如蚂蚁在巢里放置蛋,食物,垃圾的时候只遵循一个简单规则,和周围东西不一样的拿走,如果一样就放下来,蚁巢里只要有足够多的蚂蚁就能整理得大致整洁,并且达到一种动态平衡,每一时刻都会有某些东西拿起放下,但总体来看是稳定的.
首先是deneuburg提出了最基本的模型并给出了模拟单个agent记忆的函数,然后fiesta引入了neighbourhood函数,并提出了一些关于蚂蚁行为的建议,不过现得有点不必要的复杂化,最近的研究是模拟蚂蚁的信息蒙来指导蚂蚁的行为
高手就是高手，一出手就不凡啊，又快又好，呵呵，比我这抄笔记的强太多了。
老大,能不能多科普一些东东啊? 谢先.
关于蚁群算法
pdwolf老大说的非常好，非常专业。领会了其精神以后，讲一点俺自己的理解。
蚁群算法的特点是，利用信息正反馈来增强群体对于问题较优解的记忆。一个非常简单明白的生物原型是，从蚁穴到食物源有A、B两个路径，A长B短，甲乙丙三个蚂蚁去搬食物。甲乙先出发，这时选择A、B两个路径的几率是一样的，不妨设甲――A，乙――B。每只蚂蚁在其经过路径上都会释放一定浓度的信息素（外激素），而蚂蚁的生物特性会循信息素浓度大的路径前进。这样当乙已经开始返回的时候甲还在路上，这时由于B路径上已经存在信息素，而A路径上在食物源这一端还没有信息素，乙仍循B返回。当乙抵达巢穴时，丙出发，丙会循B前进，因为其路径上的信息素浓度是A的两倍。这样在大量个体下，最终所有蚂蚁都会循B前进。
对于人工模型而言，当然蚂蚁是有一定的视觉的，也就是在信息素影响下对前方进行某种程度上的启发式搜索。
蚁群算法、蜂群算法、粒子群算法都是基于种群的启发式搜索方法，我个人觉得其搜索效率比较高（尤其是粒子群），但是对复杂多峰函数的搜索，其陷入局部最优的概率大于具有交叉算子的进化算法。
俺怎么上cchere老断啊，ft。
老大能再简单介绍一下个种群搜索的区别和优点吗？ 为什么效率有高低呢？
做板凳，等着记笔记
谈一点自己的体会吧。
对于一个n维的多峰函数来说，搜索到其全局最优/次优的计算时间越少，这个算法的搜索效率可以认为越高。遗传算法/遗传规划中，目标函数的监督作用是通过选择算子淘汰弱个体来隐含实现的；蚁群和粒子群中目标函数的监督作用是根据当前个体的状态将其影响直接施加到下一代个体上。这样的结果是后者的搜索方向更直接，也就更快（粒子群的算法尤其简洁），但是更容易陷入局部最小；前者的空间遍历能力更强，也就更容易找到全局最优区域，但是一旦接近其峰点其收敛的速度就明显下降。
因此这些算法都提出了很多改进，那个文章啊，前两年期刊上真是汗牛充栋，现在明显减少了。
没说的,只有上花啦