WEB开发网
开发学院操作系统windows 2008 操作系统理论的探索 (之四) 阅读

操作系统理论的探索 (之四)

 2007-09-29 12:32:23 来源:WEB开发网   
核心提示:三、规则模型分类 -- 狭义与广义规则模型按模型整体追求的最终结果可以分为狭义规则模型与广义规则模型,1. 狭义规则模型狭义规则模型就是在如今我们的理论体系下所设计的系统模型,操作系统理论的探索 (之四),要求有预知的目的,能在可预计的时间内完成任务,才接触了一个月,很多概念尚未及消化,即要求是有限步的可计算形式,如同

三、规则模型分类 -- 狭义与广义

规则模型按模型整体追求的最终结果可以分为狭义规则模型与广义规则模型。

1. 狭义规则模型

狭义规则模型就是在如今我们的理论体系下所设计的系统模型,要求有预知的目的,能在可预计的时间内完成任务,即要求是有限步的可计算形式,如同"可有限步证明的公理体系",但被证明是不完备的。

这种模型的特点是:

系统的元素是固定的集合(固定的执行主体);

有一个固定的行为规则集合;

具有明确的可操作的系统设计目标,通常为有限个目标;

达到目标的计算必须在有限步中得到,即算法必须收敛;

结果在系统设计时可预知,即系统是可解的 ;

运行结果的分析主体是人;

整个系统的理解主体是人。

形成这些特点的主要原因是:

现有的多数系统都要求在一定时间限制内完成相应任务;

还没有很好的数学工具来分析非收敛的数据特性,目前都是尽可能的把所有计算量化成可有限计算的形式;

对人的思维研究还未深入,所有的系统结果只能由相应的人员来分析;

现有理论的积累主体是人,机器是人思维的辅助工具。

总得讲是:狭义规则模型在得到预知结果时,一个结果只对应一个规则组合序列。

对于得到结果就停止的系统而言,整个过程只产生了一条有效的新规则。

这种模型的典型代表就是图灵机。

按规则模型的角度看图灵机:

图灵机是建立在有穷执行主体和有穷规则集的基础上,对执行主体构成的有穷序列或无穷序列进行规则操作的概念机器。其判断规则就是图灵机能否停机,对于可停机的图灵计算称为是可收敛的计算,否则是发散的计算,由此产生了著名的"停机"问题。

与图灵机相关的理论在很多书中都有描述,在此就不再细述,因为篇幅过长。

图灵机所具有的一切局限性,狭义规则模型都具有,最关键的局限性就是有穷规则集。

而广义规则模型的一个特点就是动态构造无穷的规则集。

现有的关于狭义规则模型的最典型算法是遗传算法,将在下一节中讨论。

2. 理论体系发展的形式

在引出广义规则模型前,先考察一个广义规则模型的实际例子--我们的理论体系本身。

自从人类学会用文字来记录历史与知识后,人类就没有停止过建立完善的可解释世界的理论体系。

但我们建立的理论体系有如下特点:

无法预测未来理论的形式。

无法预测产生新理论的时间。

理论的产生是一小步小步的基于逻辑推理的积累。

无法预测现有理论体系外的全新理论产生的形式与时间。

这些显然于我们对具体系统设计时候要求的各种有时间限制期望目标不同,关键是没有了收敛的要求,因为无法去判断如何收敛。

而第三点积累形式与规则模型的运动过程存在一致性。

作为所有理论的基础:数学与逻辑,它们是建立在公理集上的理论体系。

对于数学与逻辑而言,相应的新定理必须是可以由已知定理或公理进行有限步推导后的结果,除非是直接将其作为一条未经证明的公理假设来使用。这一点与规则模型具有一致性。

规则模型执行主体行为规则集组合形成新的规则判断规则集
数学与逻辑理论研究对象公理集合由公理推导出的定理正误判断融合进每一推导步骤中

数学与逻辑中所有正确的定理本身包含了正确性判断,所以其判断规则是最简单的二值判断非错即正,所以无须显式的判断规则来进行推导约束。所以公理体系是规则模型的最佳形式,因为它将判断规则集完全简化,使得行为规则成为非常精确的可判断行为,虽然增加了行为规则的复杂度,但简化了新规则产生的方式,可加速新规则的产生。

由上表的比较可以看出,理论体系的发展实质是不断寻找有效规则组合的过程,即理论体系是一种特殊形式的规则模型,但它们明显不同于狭义规则模型,无具体收敛性判断,所以将它们称为广义规则模型。

3. 广义规则模型

3.1 定义

"广义"的含义就是能包含所有,没有具体的限制,与狭义规则模型的本质差别就是无收敛性约束。无收敛性约束来源于我们自身对理论体系发展的无收敛性。

广义规则模型的约定如下:

执行主体集可以是动态的可变集合,允许是元素无限的集合。

行为规则集合是无穷集合。

初始规则集仍旧是有穷集合,但每个新的有效规则组合,都作为新规则添加进初始规则集,以此使行为规则集趋向无穷集。

判断规则集是动态的可变集合,随着执行主体集合的变化而变化。

以规则模型自身完善为目标,允许对所有基础集合中的元素进行修改(删除、改善或添加)。

判断规则只限于判断新组合形式是否逻辑成立,而不判断是否该规则是否能产生可收敛的结果。

第六条的规定,是要求凡是正确的新组合形式都认为是正确的新行为规则,将其可以加入行为规则集中,使狭义规则模型中对收敛性的限制失去意义,在广义规则模型中唯一动作就是不断组合寻找新规则形式,唯一目的是通过不断产生新规则来判断整个行为规则集合是否完备,即模型的自完善目标。

广义规则模型是对我们实际的理论体系结构与发展形式的模拟。

即广义规则模型可以说是全局收敛,即不断收敛于自然规则总集。但自然规则总集本身是一个抽象的概念,所以实质是全局不收敛,符合"系统论"中的"开放式系统"的定义。

如此广义规则模型的实质就是对我们自身理论体系的模拟,对我们产生理论的形式进行模拟,所以可以说广义规则模型就是对人思维的模拟。

实际上规则模型本身就是一种广义形式,只是在实际应用中,我们添加了很多具体的约束,主要集中在判断规则集。

广义规则模型的规则组合,可以说是一种可局部收敛的形式,即产生一个有效新规则就是一次局部的规则组合收敛。但由哥德尔证明的不完备性定理表明,任何公理体系都是不完备的(在有限计算步骤下),这也是允许执行主体和行为规则集无限的原因,而不完备性是存在自身的矛盾,而这正是规则模型自身发展的契机,因为我们实际的理论体系就是如此发展的。

(相关讨论在下篇进行,需要先对人的创新思维进行分析后,才能把不完备当作契机,即如何推动广义规则模型的不断发展)

这样可以得到如下定义:广义规则模型是对现有理论体系的模型化形式

似乎口气过大,但两者的确是一致的。

按这种方式,我们可以为所有的理论体系进行数字化,形成完整的广义规则模型,当然执行主体、初始规则集与判断规则集的选取是一个很大的难题。但将其作为机器思维的一种结构有其明显价值,因为机器思维是对人思维的模拟,而广义规则模型同样是对人思维的模拟。

所以广义规则模型是机器思维的一种等价形式。

而真正能建立实用的广义规则模型前,还需要先发展狭义规则模型,使我们彻底掌握建立执行主体、初始规则集与判断规则集的方法,还有一点是需要对不完备性的更深入研究,是指将其量化成可计算的方式。

3.2 关于判断规则集

是否收敛是由判断规则来掌握的,也是狭义规则模型与广义规则模型的差别所在。

只要是判断为正确的规则组合形式就认为是该规则模型的一个新规则的生成,而把它加入规则模型的初始行为规则集中,类似于我们产生新的数学定理后,该定理便成为数学理论的一份子,实质上广义规则模型是对这一过程的模拟。

先看一个例子,法律的特点:

法律中规定的条目看似对行为的限制,实则表达的是:除了条目中限制不能做的事以外,其它都能做。

操作系统理论的探索 (之四)

人的行为集合是随着知识的逐代积累不断扩展的集合,同时推动社会不断发展,对原有的法律体系不断进行革新,因此行为集合与限制行为集合都是不断发展变化的集合,不变的是它们之间的关系。

而广义规则模型的新规则产生就是遵照了这一形式,判断规则集就如同是"法律"概念,而执行主体集合就是"人",而行为规则集合就是"人的行为集合",规则模型就是"人类的社会",只要不"违法"的新组合就是正确的"行为",便可加入"人的行为集合"中。

而规则模型的发展就如同社会的发展,执行主体集、行为规则集以及判断规则集都随着变化。从此处可以看出判断规则的重要性,是整个模型稳定发展的核心,如同法律在人类文明进步中的地位一般。

4. 关于"自然规则总集"

首先声明一点: "自然规则总集"的称呼是有问题的!

集合的概念是指众多独立元素的聚集,即使是拥有不可数元素的集合,其基本单位也是单个独立元素。

而自然界或者是宇宙,本身就是一个有机整体,是否真的存在单个独立规则?

只有在我们自己建立起来的理论体系中才把这个有机整体量化成众多可独立描述的规则。

另外自然界存在可精确表达的规则吗?

这个问题的关键在于有限与无限的关系,在我们的意识领域,最小的度量单位总是大于0的,所以我们量化的结果总是可数的,不连续的,而现实世界的最小度量单位是0,所以是连续的,这也是现在连续统中一直无法解释的问题。

虽然我们知道数轴是一条由连续点组成的直线,但我们无法说明这些点是如何连续的点靠点构成一条直线,整个世界的基本构成是连续的,就象最简单的数轴那样,而我们解释的时候总是把它们量化成可数的形式,因此我们总是在不断逼近现实,而无法彻底精确描述。

(或许在现有数学形式有重大突破后,可以解决这一难题,那时我们将掌握无限精度的技术)

还有一个很难回答的问题:自然规则总集是一个动态集合还是一个静态集合?

如果是静态集合,那就是所有的规则都是预先存在的,那它们以什么形式存在,这似乎于世界是运动着的世界有矛盾。

如果是动态集合,那就是说自然规则随着时间的推移,而不断创造着新规则,那它是如何创新的,为何要创新?

似乎,无论是何种情况都是难以理解和分析。

这些问题会导致一个疑问,自然规则是否存在?自然规律是存在的,自然规则是我们对自然规律分析量化后得到的结果如此的话,自然规律又是什么?它是如何构成的,似乎是永远也没有尽头的问题。

幸好这些问题暂时不会影响我们去建立解释世界的理论体系。

所以我们还是可以放心地称呼"自然规则总集",认为它代表了整个世界(对人而言)的组成规律,包括人类社会(人类也是这个世界的一部分)。

5. 规则组合真的能无限吗

答案是否定的!

个人的思维是无限的吗? 否!

生命是有限的,思维的速度是有限的,最快也不会超过两个神经元之间的信号传递速度,但速度是再快也是有限的。

即使假设每次两个神经元间传递一个信号都产生一次新的理论大突破,人脑的神经元是有限数的,因此人的一生所能产生的新突破也是有限可数的,所以单个人的思维是有限的(相对于整个自然规则总集而言)。

人类的思维是无限发展的吗? 否!

至少得先证明人类可以永远的繁衍下去,而且知识的世代积累不能中断(人不能通过生育直接将知识传递给下一代,至少现在是这样),然后才有资格考虑人类的思维是否能无限发展的问题。

(不过在逻辑上,这是一个很好问题,即人类的思维方式是否有了解所有自然规则的潜力)

规则集合能无限组合吗? 理论上可以,实际上不行!

除非能找到一种能永远存在的可进行规则组合的主体。

(比如整个宇宙大概可以算一个永远存在的主体,但对它来说,就没有必要去模拟自身的规律)

即使存在这样的主体按照我们现有的方式去进行规则组合,其规则组合的总数将是可数的,而自然规则是否是可数的就不得而知了。

因此,我们可以得出这样一个结论如果机器思维不能突破规则组合的形式,则其产生的新规则必然是有限的,对于其初始规则集而言,具有不完备的特性,由哥德尔在1930年证明的不完备性定理知,对于任何公理集,在进行有限步推导或计算形式下,都是不完备的。

规则模型的初始规则集就可以看成是一任意的公理集,所以它所得出的结果(在广义规则模型中的行为规则集),必然是不完备的集合,这似乎是很不幸的结果,因为自古以来我们追求的都是理论上的完美,不完备性已经让我们对自己的理论体系大感不幸。但对于机器思维来说就未必了,这将是机器思维创新的一个突破口,而这个突破口必须结合人自身的思维创新方式后才能发挥作用(下篇再继续讨论)。

四、遗传算法(GA)

在对规则模具体运行方式的可计算形式感到困惑时,发现了遗传算法,使得很多问题有了解决的可能。

1. 遗传算法简介

1.1定义

关于遗传算法的定义似乎比较少见,一些资料上虽然讲了很多具体内容,但就是没有定义,估计是比较新的分支,发展过快,所以难以定论。但都把遗传算法作为一种搜索算法。

有一个定义还是比较有代表的:

遗传算法是一种仿生优化算法[3],以生物进化理论与遗传学为理论基础。

基本思想是:从一个初始种群出发,不断重复执行选择、交叉(即杂交)和变异的过程,按优胜劣汰的原理,使种群向一个预定的目标进化。

从20世纪六十年代提出至今,已经发展成四个分支:遗传算法(GA)、进化规划(EP)、进化策略(ES)和遗传程序设计(GP),并统称为进化计算(EC)。

进化计算体系可归纳为[1]:

进化计算 = 进化算子 + 进化操作 + 选择策略 +进化计算理论

关于GA、EP、ES以及GP,在[1]中有较详细的比较。主要是细节上的差异,整个模式是相同的。

1.2 算法模式

基本算法形式如下[3]:

随机给定一组初始种群(或解);

按特定方法从当前种群中选择一定数量的个体;

对所选择的个体进行基因操作,产生新的个体;

评估个体的适应值,使用淘汰机制,形成新的种群;

检验停止准则,若满足则停止,否则返回第二步。

其中基因操作包括:交叉(即杂交)、变异等等,在下一节讨论。

与传统搜索算法比较遗传算法有如下特点:

操作对象是一组可行解,而非单个可行解,是多轨道搜索方式,具有良好的并行性;

只利用目标的取值信息,对函数性态无要求,能适于无解析表达的目标函数,具有很强的通用性;

能以较大的概率收敛到最优解或满意解,具有好的全局性和稳健性;

算法的基本思想简单,具有良好的可操作性与简单性。

1.3 一点局限性

过于拘泥于进化的形式,而没有注意进化的本质。算法始终是对进化形式的模仿,人为的设置了一个应用门槛。毕竟遗传算法的发展才刚刚起步。

一个问题:对于无生命限制的生物体,遗传与变异有何价值?

机器思维是一种相对而言具有无限生命的"生物",对它来说遗传与变异的价值在哪里?

下面我们具体讨论:生物学中的进化、遗传算法以及规则模型,三者的联系。

2. 进化的概念

生物进化是只有有限生命的生物对生命形式进行无限探索的方式,是在生命规则集合基础上进行的无限规则组合过程(如果进化是无限过程),目的是更好的生存与发展。

可以说进化是有限生命的生物在自然环境下发展的一种自适应搜索算法,试图发展出最佳的生存形式,在地球上的结果就是产生了人类。

2.1 基因的概念

基因代表的是执行主体,其对应于一个庞大而复杂的行为集合,包含自身发展的规则、与其它基因组合的规则。

细胞依靠代代自身分裂而不断发展壮大,到一定程度后便能自动转化成各种器官,现代生物学的解释是在基因的控制形成了整个生物体,即基因集合内部包含了最终结果的信息,可以说是在基因控制下达到了局部最优的状态,也可称为全局最优,因为它形成一个具体而独立的生物体,且具有生命。

但基因本身代表只是潜在的可能,进化是为了适应环境,而环境决定了整体基因的表现形式,即哪些基因会被激活,哪些基因会处于稳定的休眠状态,哪些基因会处于不稳定的随机状态,随时间与环境的变化而存在激活或休眠的可能。

从规则模型角度看,基因是最基本的执行主体,它决定了其行为规则集的范围。但对细胞来讲,染色体虽是基因组合,但也是一种执行主体,因为它决定了生物的性质,所以执行主体本身也可以是一种复杂结构,关键是设计系统时如何予以简化。也可直接使用复杂的执行主体,构成一个复合的规则模型。

在如今的遗传算法中,基因对应的是各种基因编码,淡化了基因的本来面目,因为编码的具体含义只是保存在设计者的脑中,仅从代码中是难以识别的。二进制基因编码是最常用的一种。它的产生,极大的简化了基因形式,非常适合用计算机操作,也使遗传算法能被广为应用。

具体方式是:

每个基因只能取值为0或1,然后考虑种群量的范围,如 00101就表示一个取值在[0,63]内的个体(即染色体),其第三、第五个基因的取值为1。而63表示该种群的数量上限为63个。

还有实数编码、符号编码等等,不再介绍。

2.2 杂交的概念

当生物进入生育年龄时,说明这些生物体是适合其生存环境,属于未被淘汰的生命体,通过杂交后产生的新个体,是继承了两个适合环境的生物的基因,使这个新个体可以有较好的存活可能。从物种的角度讲,是保证了优良物种生存的稳定性。

在现今的遗传算法中,杂交的概念得到了充分的体现。

从规则模型的角度看,是有效行为规则组合成新的有效的行为规则。而每个有效行为规则对应一个或多个执行主体,所以规则组合即代表了主体组合,代表了交叉过程,其结果是相关执行主体的状态变化。

执行主体的数量可以是不变的,如象棋游戏中,执行主体是双方的棋子,总数是不变的,但其状态是可变的,即该棋子所处位置,或者被吃掉。而在《上篇》的十字路口模型中,执行主体数量是可变的,即进入或离开路口的车辆与行人数量,不变的执行主体的类型。而交叉后改变的是执行主体人或车的状态。

在遗传算法中把杂交简化为交叉:

例如有两个个体A与B:

A :1010 101 , B :0110 110

将两个体的后三位基因交叉得到新个体A1与B1:

A1 :1010 110 , B1:0110 101

这就是遗传算法的交叉过程,这一过程中产生的是新个体。

遗传算法的形式是:不记录产生新个体的过程,而只保留了新个体的状态。而规则模型是保留了交叉过程,不一定产生新个体。

但这只是一种规则定义方式,对于规则模型而言,只需使用一初始规则:个体繁殖规则,允许执行主体组合产生新个体(也可以是单个执行主体),就可形成遗传算法的繁衍行为。

也可以认为只是主体状态的改变,就可把遗传算法等同,例如:认为A-〉A1 , B-〉B1 只是主体状态的变化。而遗传算法在多数情况下都保持有效个体数量不变。

所以遗传行为只是规则模型的一个简化的特例。

2.3 变异的概念

对于变异现象,似乎现代生物学中尚没有确切的解释它产生的原因。

变异有两层含义:

同一物种的基因顺序产生了变化;

基因突变,产生了新的基因。

变异发生的概率极小,且变异后的多数结果都无法生存,这是生物学里的结论。

现有遗传算法中的变异只是变异的第一层含义,没有真正意义上的突变,因为突变意味着全新的基因组合规则。例如对于一个体 A:010010 ,按小概率将其第三个基因突变,由0转成1,即得到A1: 011010 。这就是遗传算法中的突变,只改变个别基因的取值,而不产生全新的基因。而小概率行为就是对生物突变行为的模仿。

从规则模型角度看,变异的两层含义对应如下:

对新产生的有效的规则组合形式,改变其部分规则组合顺序与方式(类似于产生新定理);

对初始行为规则考察,判断是否存在产生全新的基础行为规则的可能性,即相应执行主体的行为突变(类似于产生新公理);

对执行主体集合考察,判断是否能产生全新的执行主体类型,为整个规则模型带来全新的血液,即执行主体的突变(类似于新研究领域的产生)。

即遗传算法考虑只是个体本身,而规则模型考虑的是所有可变因素。

2.4 全局约束条件

对生物基因来说,全局约束就是使得细胞最终能形成一个完整的生命个体,这种控制过程至今还是生物学中的难题,虽然现在可以认定基因中包含了这样的功能。

而在我们模拟进化的遗传算法中,算法收敛性研究可以算是对约束条件的研究,它使得到进化最终得到的是相应问题的一个优化解。这是狭义规则模型的本质特性。

但对于真正的复杂系统而言,全局约束条件的研究是研究系统的目的,如同生物基因能在全局约束下形成一个具体的生命。而仅从基因本身的形式似乎很难想象出最终的生命形式,这就成为基因研究的重大课题。

全局约束条件的相对性:

基因组成染色体,发展形成细胞,最终形成完整的生命体,这是一种自底向上分析生物体系统的方式,三个过程是生物体系统的的三个侧面。显然每个过程所具有的全局约束条件是不同的,这就是相对性,实际上是同一全局约束在不同侧面的表现形式。这点在规则模型内很重要,可起到分解环境的作用。

2.5 关于生物进化本身

进化产生了人,但有历史记载的人类社会发展了数千年,这段时间内什么是起决定作用的,是进化吗?

现在的人与两千年前的人相比,有多少差别:平均寿命增加、平均身高增加等等,但这些增加是完全是进化的功劳吗?

与过去相比总体智慧增加很多,但个人智慧是否增加了呢?智慧增加仅仅是大脑容量增加吗?

当人的进化进入一个稳定期后,我们的基因组合方式已经趋于稳定,真正改变我们自身的是长期的知识积累,以及我们长期使用知识对自身的改造,比如我们饮食习惯、生活习惯、工作方式、保健方式等等。特别是如今,基因的秘密正在被破解,或许在可以期待的未来人类整体基因组合方式会进入一个新的稳定状态(通过基因改造),但所有这些是知识积累的结果。几千年来,不断有代表相应时代的智者出现,但他们的后代往往变得与常人一样,大概是我们的进化方式还不够先进吧!幸运的是知识积累方式祢补了这一遗憾。

对于一般生物而言,它们智能水平太低(个人不认为它们没有意识),只能通过原始的活动与自然环境抗衡,不得不接受自然选择,在这种情况下,进化是物种发展的决定因素。

知识积累能力可以算是人与一般生物的重大差别(当然在破解基因之前,我们的处境与它们差别并不大)。对人而言知识的积累比进化更重要。

地球的生命形式只是是整个宇宙中众多生命形式中的一种(虽然我们还没有找到其它形式的生命),人类的产生与进化是地球上生命进化产生的局部最优点(解)。(当然不包括我们无法识别的生命形式,地球上有存在的可能,毕竟我们只知道生命形式是生物概念,而且所谓的生命特征也是我们分析自身得到的结果)

未来人类的进化结果将由我们探索宇宙和自身的结果来决定。

3. 一个结论

遗传算法由三部分组成:

基因 --执行主体;

繁衍行为(交叉、变异等)--初始行为规则;

环境模拟(选择、最终停止条件等)--判断规则。

遗传算法教完整地体现了规则模型的特征,是规则模型的一种简化形式--只保留了个体的变化数据。相对而言规则模型更强调的是过程记录,因为它是我们真正需要的知识形式,而个体的变化只是应用知识的结果。

在狭义规则模型中,遗传算法的称呼比较适合,因为所有模型都是为特定问题而设计的,具有自己的生命时限(收敛性),属于有限生命形式的进化范畴。

在广义规则模型中,遗传算法则等价于考察无限生命形式的自我发展方式,因为生命无限,进化的形式变得不在重要,需要的是进化的本质--不断寻找有效基因组合形式的过程,并转换成更重要的知识积累方式。

说有效而不是最佳是因为环境是动态变化的,所以只存在有效,而不是最佳,这点在NFL定理[2]中得到了很好体现。

(NFL定理指出:在进化算子中,不存在万能的"最佳"算子)

但遗传算法的规则组合模式非常清晰,该模式不依赖于具体问题,而一般系统模型都只是局限于自身的应用领域,向其它领域推广较难,而遗传算法具有的一般性,能更方便地与具体应用结合,也是规范规则模型概念的有力工具。

因此在规则模型的概念下:

遗传算法可适用于任意按规则模型建立起来的应用系统,包括理论体系如数学与逻辑等体系。

现在的遗传算法只是狭义规则模型中简单的表现形式,而我们建立理论体系的过程是最佳的广义规则模型表现形式,它还有一个很漫长的发展过程。

4. 未来的方向--模式遗传

是遗传算法(GA)、进化规划(EP)、进化策略(ES)三者的结合,并与遗传程序设计(GP)结合的过程,因为GP的本质代表着人工智能的一个中间目标--自动编程。

人工智能以模拟人类思维是最终目标,自动编程是机器思维的最核心功能,没有它机器思维就难以真正完成复杂任务。可以想象具有模拟思维的机器,却无法自己生成所需代码,如完善自身系统的代码,那样的智能只是低级智能形式。

自动编程有两种方式:

人为的分析出所有的编程模式,机器只需分析出每个任务所对应的具体模式,然后按程序机械形成代码实体;

人提供机器的是分析问题模式的方法和简单模式的自动编程步骤,即提供一个初始集合,由机器自己产生新的模式。

第二种方式的本质是把算法本身作为进化的目标,自动寻找"好"的遗传算法来解决相应问题。

这就是未来的方向:模式遗传 -- 对算法模式进行选择、交叉、变异。

模式遗传的最佳结果是把整个程序作为遗传中的基因来进行操作,而不象现在,遗传算法只是程序中的一部分。

自动编程的关键在于是如何产生新的程序模式,是简单的复合,还是能完全创新。即使是简单复合也很有难度,不过可等同与规则组合的模式。

遗传算法对于实际应用来说是产生了一种好方法,但对理论研究来讲是一种挑战,我们必须探询该算法的本质根源,个人观点:遗传算法是人类创新思维的又一次体现。 (将在下篇中展开关于创新的讨论)

五、二论规则模型

从遗传算法中吸取的营养可以让我们非常顺利的进一步探索规则模型具体形式。

1. 静态结构

规则模型的静态结构是通过如下分析步骤逐步产生三个基础集合:

主体提取--〉主体属性--〉主体的行为规则--〉多主体结合的规则--〉判断规则 。

很容易注意到执行主体与行为规则描述的是同一概念的两个侧面。

引用程序设计的用语--类设计的概念,执行主体与行为规则构成一个完整的主体类,而系统中的执行主体只是类的实体。

(但实际应用中往往是主体与行为相分离的的而简化程序编码量,如遗传算法中,主体被简化成二进制编码或浮点编码,侧重于直接按其数值定义域的表现形式来描述,而行为规则如:交叉、变异更是直接在代码中独立使用,不过比较容易规范)

判断规则对应的是进化环境,它本身是一个类--"环境"类。"环境"对应的就是全局约束。

规则模型的静态结构就是由这两种类集合构成--主体类集合与"环境"类集合。

对于狭义规则模型,一般只有一个"环境"类,而拥有一个或数个主体类。如遗传算法中只有一个主体类。

而对于广义规则模型,因为是对人思维的模拟,所以环境很复杂,总是按现有的知识形成几个"子环境",如同我们的理论体系那般划分各自地盘。

但"环境"类的形成是一个复杂的量化问题,主要问题有两个:

直接使用判断规则比构造"环境"类简单了无数倍。如现在的遗传算法那样,判断规则都是直接使用,而环境只存在于设计者的大脑中(多数系统都是这样做的)。如从机器思维的角度出发,这一量化过程是必须的。

主体们与环境的关系表达非常困难。因为环境是一个动态概念,是随着主体的运动而变化,是一个开放式系统。而主体之间的关系是在环境中形成,所以可通过"主体-环境"的关系来化简,所以相对容易考虑。

在遗传算法中提供了一种简单的环境处理方式:

遗传算法本身的选择方式就是一种模拟生存竞争的环境形式,是一个大的虚环境,而具体的应用环境通过停止准则来独立表现,虽然算法中是规则地直接使用,但因为遗传算法本身模式非常清晰与简洁,所以停止准则地使用相对比较独立,可以在相应位置使用"子环境"的概念来构成小的实环境。

这种方式适合于狭义规则模型,而对于广义规则模型,因为是多个"环境"的复合,可以先简单地看成是多个相对独立的狭义规则模型的组合,是多个小的实环境在一个大的虚环境下的组合。不过,现今我们自己的各种理论体系都没有找到好的一体化的形式,虽然公理体系的出现带来了希望,但多数领域内对公理体系的认识与应用几乎没有、或者是初步,只有少数几个领域比较完善,如数学、逻辑、部分物理理论等等。

2. 动态结构

规则模型的动态结构是其运行方式,实质上就是一种搜索算法。

可简单地分为两种:

主动搜索形式。

针对狭义规则模型中明确的"环境"形式,即已经存在可穷举法(或无限穷举)的可能。而使用规则模型,如遗传算法,只是一种加速搜索的方法。这种形式,需要设计者首分析出确解集合的范围以及解的精确度,才能在算法中实现类似与遗传算法中的编码环节。而且编码的精确是关键的,否则难以得到最优解,精确不够会导致局部最优解都得不到。

被动搜索形式。

针对"环境"概念难以明确的规则模型,特别是广义规则模型。从上一章中讨论可以看出,基因只代表可能,决定基因表现的关键是生存环境,这也是具有复杂"环境"的规则模型运行的关键--外部推动力。

把复杂的"环境"简化为数个典型问题,构成一个问题集,以此作为规则模型的外部推动力,而"环境"复杂度取决与问题集合的复杂度,通过不断扩大问题集逼近实际的复杂"环境"。如此把规则模型简化成一种类似多目标的规划问题,实质是多狭义规则模型组合形式。

解决一个问题能得到一个新的有效规则,它们中每一个都代表了一种问题的求解模式。

这样产生的新规则比随意组合生成的新规则更有效,因为与该规则对应的问题是已知的,而随意组合产生的新规则,缺乏目的性,要分析出其所对应实际问题的特征非常困难。按问题求新规则的形式也是我们形成现有各种理论的基本方法。

而每个问题都代表着整个复杂系统的部分特征,即是全局约束条件的一个表现子集。在问题已知的情况下,分析求解该问题的新规则,就等同于分析该全局约束子集的特征。通过积累全局约束条件的特征,可以帮助我们逐步展现整个复杂系统。

所以我们可把问题归结到特征(即模式)提取的范畴。(模式是下篇的一个讨论主题)

如下示意图:

操作系统理论的探索 (之四)

参考资料

王小平、曹立明.《遗传算法--理论、应用与软件实现》. 西安交通大学出版社,2002

李敏强、寇纪凇、林丹.《遗传算法的基本理论与应用》. 科学出版社,2002

张文修、梁怡.《遗传算法的数学基础》. 西安交通大学出版社,2000

杨东屏、李昂生.《可计算性理论》. 科学出版社,1994

注:

对于遗传算法,才接触了一个月,很多概念尚未及消化,有误解处请各位指出。

Tags:操作系统 理论 探索

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接