倒数第一篇:11.3  仿真结果
第一篇:《用 于 最 优 化 的 计 算 智 能》
主页
第三篇:1. 2  最优化技术综述
第四篇:1. 3  本书的结构
文章列表

第 1 章  引  言

《用于最优化的计算智能》 Nirwan Ansari Edwin Hou 著 李军 边肇祺 译 清华大学出版社

许多科学和工程问题都可以归结为有约束条件的最优化问题,并可用如下数学公式加以表达:

mx∈iSnf(x) 基于g(x) (1.1)其中S 是解域,f 是价值函数,g 是约束条件集合。各种最优化问题可以根据S,f 和g 的特点加以分类。如果f 和g 都是线性函数,则(1.1)式所描述的是一个易于求解的线性最优化问题。否则,(1.1)式便成为较难解决的非线性最优化问题。线性规划是一类典型的线性最优化问题,其约束条件的形式为g(x)≥0或g(x)= 0。线性规划问题可以用很简单的算法[125]求解,并能在有限步骤内求得最优解。然而,在工程和其它领域中遇到的问题有很多都属于“难于求解”的一类问题,无法使用确定性算法求解。例如旅行商问题(TSP)和各种调度问题等。

包括神经网络、模拟退火、随机机、均场理论和遗传算法在内的各种最优化新方法的发现和发展,使得更有效地求解那些可以良好定义的难题成为可能。本书就以这些新的最优化方法和它们的应用为主题。

1. 1  计算复杂度

在很多情况下,一个最优化问题可以用许多方法加以解决,而每种方法又能够采取多种算法予以实现。由于所有这些算法全都可能给出同一最优解,人们需要根据求得最优解的效率对它们进行分类。当然,一个最优化问题也有可能根本难以解决,因而不存在有效的寻求最优解的方法。计算复杂度理论就是用于研究算法有效性和问题难度的手段[57][94][110]。这一节主要介绍有关计算复杂度理论的一些基本概念。

1.1.1  算法分析

为便于有效地对算法进行真实比较,我们假定编译效率、程序语言以及计算机运算速度等因素对于有关算法来说都是完全相同的。

算法所用时间或空间随问题变大的增长率是衡量算法有效性的一个重要尺度。问题的“大小”是以输入数据量来计算的,例如旅行商问题中城市的数目。算法占用的时间和空间,亦即算法的时间复杂度和空间复杂度,则取决于算法用于求解问题所需的计算机运行时间和存储空间。研究一个算法随问题的规模增长时的极限性能,即渐进时间/空间复杂度,也是很有意义的。

我们可以定义一个以数据量为输入,时间/空间占据量为输出的函数,用来度量算法的量化时间/空间复杂度。例如,需要求解的问题是将一组整数由小到大排序。解决手段

#第1页-

之一是利用冒泡排序算法[10]比较相邻两数并进行适当交换。冒泡排序算法在最坏情况下

的时间复杂度可以表示为

n(n- 1) n2 n

f(n) = 2 = 2 - 2 (1.2)

其中n是被排序整数的个数。

下表所列正是冒泡排序算法在不同输入数据量下的时间复杂度,它显示出每当输入

量增加一个数量级时,冒泡排序算法的时间复杂度大致增加两个数量级。换句话说,时间

复杂度以n的二次指数增长,对应于(1.2)式函数中的二次项n2/2。

1 10 100 1000 10000 105 t

f(n) 0 45 4950 499500 5.0 107 5.0 109 G

由于算法的渐进复杂度是我们关注的对象,余项- n/2可以忽略不计,而二次项中的

常数因子1/2也可省去,因此,冒泡排序算法的时间复杂度为 2 数量级,或记为 ( 2)。

n O n

定义1.1  若f 和g 是定义在正整数域上的正函数,f,g:I+ →R+ ,则

(1) f= O(g),如果存在正常数c和N,对所有的n≥N 都使得f(n)≤c・g(n)。

(2) f= Ω(g),如果存在正常数c和N,对所有的n≥N 都使得f(n)≥ c・g(n)。

(3) f= (g),如果存在正常数c,d 和N,对所有的n≥N 都使得d・g(n)≤f (n)≤

c・g(n)。

例如,(1.2)式中有

n(n- 1) ≤n,其中n≥12

2

因此可有c= 1和N= 1,使得f= O(n)。2

在很多情况下,算法的复杂度为下列函数之一:

O(logn),O(n),O(nlogn),O(n),O(2),O(n2 n logn),O(n!),O(nn)

要注意的是,上述函数是按复杂度增大排列的。

表1.1  时间复杂度函数的比较

输入量n

时间复杂度

函数 10 20 30 40 100 E

n 10ns 20ns 30ns 40ns 100ns hR

nlogn 10ns 26.0ns 44.3ns 64.1ns 200ns :¥

2 100ns 400ns 900ns 1.6μs 10μs i

n 4.0

2 1.0μs 1.0ms 1.1s 18.3min

世纪

77.1 8.4 1013 2.6 1029 3.0 10139 b

n! 3.6ms 年 世纪 世纪 世纪 v

表1.1在假定所用计算机每秒可以执行10亿次运算的前提下,比较了几个方程在不

#第2页-

同输入量条件下的时间复杂度。很明显,如果一个算法的复杂度是指数函数(例如2n 或n!),它在大输入量情况下是无望求解的。当一个算法的时间复杂度方程可以用多项式方程来划界时,我们称之为多项式时间算法; 否则,它是一个指数时间算法。

1.1.2  NP 完全问题

如上所述,多项式时间算法比指数时间算法易解得多。不过总是有一些最优化问题无法用多项式时间算法求解。这些问题被称为难解问题。事先了解一个问题是否为难解问题自然会有很多好处。NP 完全理论的建立就是为了确定问题的难解度,并检验各个问题在难易程度上的相互关系。这一NP 完全理论的基础是由库克(Cook)[46]确立的。

(1) 如果一个问题P 可以被一个多项式时间算法求解,而另一个问题Q可以在多项式时间内被变换为P,则一定存在一个多项式时间算法可以求解Q。其中在多项式时间内将一个问题转换到另一个问题的过程称为多项式时间约化。

(2) 决策问题(答案为“是”或“否”的一类问题)中可在多项式时间内用非确定性计算机① 解出的特定类型被称为 。

NP

(3) NP 中的任一问题都可以被多项式约化为NP 中的一个特定决策问题,即满意度问题。因此,如果可以找到一个多项式时间复杂度算法来解决这一满意度问题,则NP 中的任一问题都可在多项式时间内得解。另一方面,如果NP 中任一问题是难解问题,则此一满意度问题也是难解问题。满意度问题可被认为是NP 中“最难”的问题。

(4) 存在一组使NP 中的其它问题以多项式方式约化于它们的“最难”问题。

有很多优化算法,诸如旅行商问题、多处理器任务调度问题等,都被发现可以多项式约化为NP 中最难的问题。这些问题构成了NP 完全问题类。在文献[57]中可以查到它们。究竟NP 完全问题是否难解仍然是个谜。虽然很多线索表明NP 完全问题确为难解,但至今未见严格的证明或证伪。不过,如果可以表明一个问题属于NP 完全问题类,它多半是难于求解的。