计算机中非数值数据的编码,非数值算法

非数值算法，是根据对象的不同，分为数值并行算法和非数值并行算法两种中的一种。

中文名

非数值算法外文名

Non-numerical Algorithm

分    类

数值并行算法，非数值并行算法

非数值算法定义

语音

并行算法根据对象的不同分为数值并行算法和非数值并行算法两种。

多项式与线性代数方程组，矩阵与非线性方程，插值、逼近及其应用，数字信 处理，小波变换，快速傅利耶变换等内容属于数值算法。非数值算法一般包括线性表、栈、队列和串，树，图，排序、查找与文件操作，并行算法等，主要是为符 运算而设计的并行算法。

常用的非数值并行算法有模拟退火算法、遗传算法、神经 络算法等[1]

。

非数值算法模拟退火算法

语音

1、模拟退火算法可以分解为解空间、目标函数和初始解三部分。

非数值算法解空间

它为问题的所有可能(可行的或包括不可行的)解的集合，它限定了初始解选取和新解产生时的范围。对无约束的优化问题，任一可能解(possiblesolution)即为一可行解(feasiblesolution)，因此解空间就是所有可行解的集合；而在许多组合优化问题中，一个解除满足目标函数最优的要求外，还必须满足一组约束(constraint)，因此在解集中可能包含一些不可行解(infeasibleso1ution)。为此，可以限定解空间仅为所有可行解的集合，即在构造解时就考虑到对解的约束；也可允许解空间包含不可行解，而在目标函数中加上所谓罚函数(penaltyfunction)以“惩罚”不可行解的出现。

非数值算法目标函数

它是对问题的优化目标的数学描述，通常表述为若干优化目标的一个和式。目标函数的选取必须正确体现对问题的整体优化要求。例如，如上所述，当解空间包含不可行解时，目标函数中应包含对不可行解的罚函数项，借此将一个有约束的优化问题转化为无约束的优化问题。一般地，目标函数值不一定就是问题的优化目标值，但其对应关系应是显明的。此外，目标函数式应当是易于计算的，这将有利于在优化过程中简化目标函数差的计算以提高算法的效率[2]

。

非数值算法初始解

基本思想：

(1)初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L。

(2)对k=1，，L做第(3)至第6步。

(3)产生新解S′。

(4)计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数。

(5)若Δt′

(6)如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。

(7)T逐渐减少，且T->0，然后转第2步。

非数值算法遗传算法

语音

遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。

Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些能适应环境的个体特征方能保留下来。

Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。

遗传算法简称GA(GeneticAlgorithm)，在本质上是一种不依赖具体问题的直接搜索方法。

非数值算法原理

遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

长度为L的n个二进制串bi(i=1，2，…，n)组成了遗传算法的初解群，也称为初始群体。

在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：

(1)选择(Selection)

这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differentialreproduction)。

(2)交叉(Crossover)

这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。

(3)变异(Mutation)

这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。

非数值算法特点

(1)遗传算法从问题解的中集开始嫂索，而不是从单个解开始。

这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。

(2)遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。

由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。

(3)遗传算法有极强的容错能力。

遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。

(4)遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。

这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的覆盖。

非数值算法神经 络算法

语音

“人工神经 络”(ARTIFICIALNEURALNETWORK，简称A.N.N.)是在对人脑组织结构和运行机智的认识理解基础之上模拟其结构和智能行为的一种工程系统。早在本世纪40年代初期，心理学家McCulloch、数学家Pitts就提出了人工神经 络的第一个数学模型，从此开创了神经科学理论的研究时代。其后，F.Rosenblatt、Widrow和Hopf、J.J.Hopfield等学者又先后提出了感知模型，使得人工神经 络技术得以蓬勃发展。神经系统的基本构造是神经元(神经细胞)，它是处理人体内各部分之间相互信息传递的基本单元。据神经生物学家研究的结果表明，人的一个大脑一般有1010～1011个神经元。每个神经元都由一个细胞体，一个连接其他神经元的轴突和一些向外伸出的其它较短分支——树突组成。轴突的功能是将本神经元的输出信 (兴奋)传递给别的神经元。其末端的许多神经末梢使得兴奋可以同时传送给多个神经元。树突的功能是接受来自其它神经元的兴奋。神经元细胞体将接受到的所有信 进行简单地处理(如：加权求和，即对所有的输入信 都加以考虑且对每个信 的重视程度——体现在权值上——有所不同)后由轴突输出。神经元的树突与另外的神经元的神经末梢相连的部分称为突触。

非数值算法工作原理

人工神经 络首先要以一定的学习准则进行学习，然后才能工作。现以人工神经 络对手写“A”、“B”两个字母的识别为例进行说明，规定当“A”输入 络时，应该输出“1”，而当输入为“B”时，输出为“0”。所以 络学习的准则应该是：如果 络作出错误的的判决，则通过 络的学习，应使得 络减少下次犯同样错误的可能性。首先，给 络的各连接权值赋予(0，1)区间内的随机值，将“A”所对应的图象模式输入给 络， 络将输入模式加权求和、与门限比较、再进行非线性运算，得到 络的输出。在此情况下， 络输出为“1”和“0”的概率各为50%，也就是说是完全随机的。这时如果输出为“1”(结果正确)，则使连接权值增大，以便使 络再次遇到“A”模式输入时，仍然能作出正确的判断。如果输出为“0”(即结果错误)，则把 络连接权值朝着减小综合输入加权值的方向调整，其目的在于使 络下次再遇到“A”模式输入时，减小犯同样错误的可能性。如此操作调整，当给 络轮番输入若干个手写字母“A”、“B”后，经过 络按以上学习方法进行若干次学习后， 络判断的正确率将大大提高。这说明 络对这两个模式的学习已经获得了成功，它已将这两个模式分布地记忆在 络的各个连接权值上。当 络再次遇到其中任何一个模式时，能够作出迅速、准确的判断和识别。一般说来， 络中所含的神经元个数越多，则它能记忆、识别的模式也就越多。

非数值算法特点

人工神经 络是由大量的神经元广泛互连而成的系统，它的这一结构特点决定着人工神经 络具有高速信息处理的能力。人脑的每个神经元大约有103～104个树突及相应的突触，一个人的大脑总计约形成1014～1015个突触。用神经 络的术语来说，即是人脑具有1014～1015个互相连接的存储潜力。虽然每个神经元的运算功能十分简单，且信 传输速率也较低(大约100次/秒)，但由于各神经元之间的极度并行互连功能，最终使得一个普通人的大脑在约1秒内就能完成现行计算机至少需要数10亿次处理步骤才能完成的任务。

人工神经 络的知识存储容量很大。在神经 络中，知识与信息的存储表现为神经元之间分布式的物理联系。它分散地表示和存储于整个 络内的各神经元及其连线上。每个神经元及其连线只表示一部分信息，而不是一个完整具体概念。只有通过各神经元的分布式综合效果才能表达出特定的概念和知识。

由于人工神经 络中神经元个数众多以及整个 络存储信息容量的巨大，使得它具有很强的不确定性信息处理能力。即使输入信息不完全、不准确或模糊不清，神经 络仍然能够联想思维存在于记忆中的事物的完整图象。只要输入的模式接近于训练样本，系统就能给出正确的推理结论。

正是因为人工神经 络的结构特点和其信息存储的分布式特点，使得它相对于其它的判断识别系统，如：专家系统等，具有另一个显著的优点：健壮性。生物神经 络不会因为个别神经元的损失而失去对原有模式的记忆。最有力的证明是，当一个人的大脑因意外事故受轻微损伤之后，并不会失去原有事物的全部记忆。人工神经 络也有类似的情况。因某些原因，无论是 络的硬件实现还是软件实现中的某个或某些神经元失效，整个 络仍然能继续工作。

人工神经 络是一种非线性的处理单元。只有当神经元对所有的输入信 的综合处理结果超过某一门限值后才输出一个信 。因此神经 络是一种具有高度非线性的超大规模连续时间动力学系统。它突破了传统的以线性处理为基础的数字电子计算机的局限，标志着人们智能信息处理能力和模拟人脑智能行为能力的一大飞跃。

参考资料

1.

詹原瑞, 张建龙. 信用风险优化中的期望短缺模型及基于非数值算法求解[J]. 系统工程理论与实践, 2005, 25(5):63-67.

2.

陈国良. 非数值计算的并行算法(上)[J]. 计算机研究与发展, 1988(11).

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34583 人正在系统学习中