Algorithm 版 (精华区)

发信人: zjliu (秋天的萝卜), 信区: Algorithm
标  题: Genetic Algorithms(遗传算法)--2 搜索空间
发信站: 哈工大紫丁香 (Mon Sep 23 17:37:10 2002) , 转信



续前(第一次翻译,请大家指点)
谢谢
QQ:16748251
http://wangzhengyao.xiloo.com
--------------
III搜索空间
搜索空间（Search Space）
在很多情况下,我们解决一个问题就是从一大堆的数据中寻找一个解，而通常这个解都是
混杂在数据中的。所有可行解（Feasible Solution可行解就是满足了一定约束条件的解
）组成的空间称之为搜索空间（也可以称之为状态空间）。搜索空间中的每一个点都是
一个可行解。没一个可行解都可以被它的函数值或者它的适应度所标记。记住：问题的
解就是搜索空间中的一个点，于是我们就是要从搜索空间中找到这个点。
这样，求解问题就可以转化为在搜索空间中寻找极值点（最大值或者最小值点）。搜索
空间在求解问题时可能是完全已知的，但一般的说我们只知道一些孤立的点，然后我们
逐渐地生成其它点。问题是，这个搜索过程可能很复杂，我们甚至不知道该去哪里搜索
或者该从是么地方开始搜索。事实上，有很多寻找合适解（注意：不一定是最优解）的
方法，比如说爬山法（Hill Climbing）
禁止接近法(Tabu Search),模拟退火算法(Simulated Annealing)以及遗传算法等等.用
遗传算法求解出来的解一般被认为是一个比较好的解,因为我们没有办法证明它是最优解
.
NP难题(NP-hard)
举一个比较难的NP问题,这个问题无法用传统的方法解决.
我们知道很多问题有快速的算法(多项式算法).但是,也有很多问题是无法用算法解决的
。事实上，已经证明很多问题不可能在多项式时间内解决出来。
但是，有很多很重要的问题他们的解虽然很难求解出来，但是他们的值却是很容易求可
以算出来的。这种事实导致了NP完全问题。NP表示非确定的多项式（Nondeterministic
 Polynomial），意思是这个问题的解可以用非确定性的算法猜出来。如果我们有一个可
以猜想的机器，我们就可以在合理的时间内找到一个比较好的解。
NP-完全问题学习的简单与否，取决于问题的难易程度。因为有很多问题，它们的输出极
其复杂，比如说人们早就提出的一类被称作NP-难题的问题。这类问题不像NP-完全问题
那样时间有限的。
因为NP-问题由上述那些特征，所以很容易想到一些简单的算法――把全部的可行解算一
遍。但是这种算法太慢了（通常时间复杂度为O（2^n））在很多情况下是不可行的.
现在,没有知道有没有那种精确的算法存在。证明存在或者不存在那种精确的算法这个沉
重的担子就留给了新的研究者了，或许你就是J。现在很多人认为那种精确的算法是不存
在的，所以他们试图寻找一种替代的算法――比如说这里的遗传算法。
这里的NP-问题的例子，旅行商问题（Travelling Salesman Problem）或背包问题（kn
apsack problem），都是满意性问题。
NP问题的简述你可以在这里看到。


--

FTP 地址改变,请注意!!!!!

计算数学与数学软件Mathematica 的FTP:
ftp://202.200.239.125    user=password= temp
Homepage: http://202.200.239.125;
※ 来源:·交大兵马俑BBS站 bbs.xjtu.edu.cn·[FROM: 202.200.239.125]
--
※ 转载:·交大兵马俑BBS站 bbs.xjtu.edu.cn·[FROM: 202.200.239.125]




--

※ 来源:．哈工大紫丁香 http://bbs.hit.edu.cn [FROM: 202.118.229.86]