２基本遗传算法的工作步骤-altium_designer6.9经典教程

第１３章遗传算法及应用简介１３．１引言１３．１．１遗传算法的基本思想遗传算法（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ，ＧＡ）是由美国密西根（Ｍｉｃｈｉｇａｎ）大学，ＪｏｈｎＨ Ｈｏｌｌａｎｄ教授等创立的一类仿生型的优化算法（ＨｏｌｌａｎｄＪＨ，１９７５）。遗传算法的思想源于自然遗传。为了说明其基本思想，下面先看一个老鼠的例子。在任意给定的时刻，有一群老鼠，其中有一些老鼠比较机灵、敏捷，这些机灵、敏捷的老鼠不易被猫抓住，于是这些老鼠多数就会生存下来，当然一些反应迟钝的老鼠也可能活下去，但这仅仅是它们运气好而已。老鼠开始繁殖，这导致了老鼠的基因物质更好地结合，迟钝的和敏捷的、敏捷的和敏捷的、机灵的和笨的等相互结合，结果小鼠群将会比初始群体的老鼠更敏捷、更机灵。因为它们的双亲一般都是敏捷机灵的，都躲过了猫的追捕。这样一代一代传下去，每一代都比其父辈更机敏，其他生物也有类似过程。这就是自然选择中的“优胜劣汰、适者生存”的自然法则。遗传算法就是对这种自然过程的模拟，将其抽象、简化，形成形式上的一种优化方法。它把问题的一个可能解表示为一个个体（Ｉｎｄｉｖｉｄｕａｌ），若干个个体组成群体（Ｐｏｐｕｌａｔｉｏｎ，称为种群），每个个体用一个染色体（Ｃｈｒｏｍｏｓｏｍｅ）表示（注意，这里把一个个体和染色体等同起来，即每个个体只有一个染色体，这与实际生物有很大区别，比如每个人有２３对（４６个）染色体），染色体由基本单元———基因（Ｇｅｎｅ）构成。一个基因控制一个或几个特征（如模型中的某个参数）的遗传，一定特征的基因被定位在染色体的一定位置上。通过在染色体上进行的遗传、进化、优胜劣汰，得到最优染色体，即最优解。简略地说，遗传算法是以达尔文的生物进化论和孟德尔遗传变异理论为基础，模拟生物界进化过程，自适应、启发式、全局优化的搜索算法。遗传算法瞄准的是那些复杂问题，它依赖于概率，又不同于随机算法，把启发性指导与随机算法有机结合，使其更具有鲁棒性；它的另一个特点是始终保持一组（而不是一个）可能的结果，从而保证可在全局范围内搜索，得到全局最优解，而不需要被优化的对象具有连续、可导等先验条件。总之，遗传算法在思路上突破了以往最优化方法的框架，以其极强的解决问题的能力和广泛的实用性渗透到科研和国民经济的各个领域，如工程优化、神经网络、机器学习、机器人轨迹设计、故障诊断、作业调度、最优控制、模型辨识、模式识别、电路设计等领域，都得到了成功的应用。近几年来，其应用领域远远突破了控制工程的范畴，在生物、环保、社会、经济、金融、市场贸易等领域也引起了广泛的注意并得到成功的应用。本章只简单地介绍遗传算法的基本概念、工作步骤和一些应用，为进一步学习和研究打下最基本的基础。 １３．１．２基本遗传算法的工作步骤基本遗传算法（ＳｉｍｐｌｅＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ，ＳＧＡ）的结构和进化过程的结构一样，也是一种迭代结构。在迭代值为ｔ时（常称为第ｔ代），遗传算法保留一组可能的结果（一组染色体向量———第ｔ代群体），记为Ｐ（ｔ）＝（ｘｔ１，…，ｘｔｎ），每个染色体向量ｘｔｉ都是问题的一个可能的结果，即一个可·１１２·