1。2 国内外研究现状及存在的问题
1。2。1 国外研究历程
1。2。2 国内研究历程
1。3 本文的主要内容
从第二章开始,我们首先描述遗传算法的基本思想和原理,以及遗传算法的基本操 作流程,这是我们使用遗传算法解决背包问题的基础。第三章将先阐释背包问题,然后 详细述说对遗传基因的编码,对遗传算子的选择,控制参数的确定,以及对于约束问题 的处理。第四章将使用测试函数对我们设计的遗传算法进行检测。使用通过检测的遗传 算法,观察其在不同参数以及初始条件下,对背包问题求解的过程,并分析实验结果。
第二章 遗传算法的基本思想
2。1 遗传算法的产生与发展
早在 1950 到 1960 年间,就已经有学者开始了早期进化算法的研究,当时是由几位 计算机科学家独立进行的,他们想将进化的思想发展成解决优化问题的工具,他们将这 项研究称为“人工进化系统”。这便是遗传算法的初始形态。
到了 20 世纪 70 年代初期,美国的 Holland 建立了较为完整的理论和方法,并出版 了《自然与人工系统的适应性行为》(Adaptation in Natural and Artificial System)一书[9]。 Holland 将这种算法正式命名为遗传算法,并且通过对遗传算法的研究将其利用到优化 问题的求解中,甚至尝试使机器利用遗传算法获得自主学习的能力。Holland 当初的基 础理论直到现代依然被学者们广泛使用,可见 Holland 对遗传算法做出来的贡献之大[9]。
几十年来,遗传算法日趋成熟,无论是用来解决实际问题还是用来建模,其应用范 围都在不断扩展。正是目睹了遗传算法的优秀能力,很多学者认为这位人工智能的产生 提供了一条行之有效的途径,他们希望计算机通过不断进化的算法来获得智能,这使人 们对遗传算法的研究热情日益高涨。
2。2 遗传算法的基本思想
由于遗传算法的思想来源于自然进化,我们就先从生物进化理论和遗传学的基本知 识开始讲起,这有助于我们更好地学习遗传算法。
从最原始的地球开始出现的原始生物,到现代社会的生物种类复杂繁多,更是出现 了先进的生物——人类,这一切都是生物自身经历了长期进化过程的演变,逐渐进化以 适应自然环境的结果。达尔文(1858 年)用自然选择对此作出了解释,表面上是生物为 了适应自然而造成的,其实也可以看出是自然对物种进行了有方向的选择,这才造成了 这样的结果,这正解释了生物的进化的原因。其自然选择学说主要分为以下三个方面[10]:
(1)遗传(heredity) 这是生物的普遍特征,由于有性生殖是通过把父代的遗传 信息复制过来并继承给子代,所以父代与子代之间拥有高程度相似的特性,这也就是我 们俗话中所说的种瓜得瓜,种豆得豆。正是遗传的这一特征,才保持了物种的稳定性, 在一定程度上可以说,只有获得稳定的子代,才是正确的遗传方式。
(2)变异(variation) 通过遗传连接的父代和子代之间具有高度的相似性,但并 不是说父代与子代就是完全一样的,他们之间总是或多或少地存在着某些差异,这种差
异是由一种现象产生的,我们把这种现象,称为变异。这一现象是随机发生的,而且是 不可预测其方向的,但是正是由于变异的存在才使得生物群体中的物种产生了多种多样 的特征,这也保证了生物的多样性。 Matlab遗传算法在背包问题中的应用(3):http://www.youerw.com/zidonghua/lunwen_100127.html