对传统拓扑算法进行改进

1. 拓扑优化的优化方法

目前连续体拓扑优化方法主要有均匀化方法 、变密度法 、渐进结构优化法 （ESO）以及水平集方法和丛宽 等。离散结构拓扑优化主唤亮要郑埋是在基结构方法基础上采用不同的优化策略（算法）进行求解，比如程耿东的松弛方法 ，基于遗传算法的拓扑优化 等。

2. 如何用分组方法计算2层对象之间的拓扑

如何用分组方法计算2层对象之间的拓扑?1.删边法：
由于每一条拓扑子路径的首节点的入度为0，因此可以采取如下办法：

步骤1：从图中选择一个入度盯缓为0的点且输出之
步骤2：从图中删除该节点及其所有出边（即与之相邻的所有点入度-1）
反复执行这两个步骤，直至所有节点都输出，即整个拓扑排序完成；或者直至剩下的图中再没有入度为0的节点，这就说明此图中有回路，不可能进行拓扑排序。

1.2 算法时间复杂度分析：统计所有节点入度的时间复杂性为（VE）；接下来删边花费的时间也是（VE），总花费时间为O（VE）。

1.3 优化：使用队列保存入度为0的顶点，则可以将这个算法复杂度将为O（V+E）。

2.采用DFS计算拓扑排序：
一个有向图是无回路的，当且仅当对图进行DFS遍历时没有反向边B。那么，怎样发现反向边呢？方法很简单：调用DFS（y）算法计算y可达的节点集。若x在该节点集，则<x,y>为反向边，时间复杂度为O（E）。

2.1 由此可以得枣游到用DFS算法计算拓扑方案的方法：以访问一个节点算凳则销作一个时间单位，把遍访了u的后代的时间称作结束时间f[u]，（f[u]可以通过DFS算法得到）。显然，对图进行DFS遍历时没有反向边B，即对于图中的任意边（u，v），都有f[v] < f[u]。

2.2 时间复杂度分析：DFS的运行时间为O（E），每个节点压入topo栈的时间为O（1），因此执行拓扑排序所需的总时间为O（E）。

3. 求拓扑排序算法的详细讲解

3.1AOV网

在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在有向图中若以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称为AOV网。如下图是计算机专业课程之间的先后关系：

基础知识课程应先于其它所有课程，pascal语言课程应先于数据结构。

3. 2 拓扑排序

在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。如上图的拓扑排序

基础知识；Pascal；数据结构；离散数学。或

基础知识；离散数学Pascal；数据结构。

拓扑排序的方法和步骤：

（1）在图中选一个没有前趋的顶点并输出之

（2）删除该顶点及由它发出的各边，直到图中不存在没有前趋的顶点为止。

若图中存在回路，拓扑排序无法进行。

以下是将一AOV网进行拓扑排序的算法：

网采用邻接矩阵A表示,若a[i，j]=1，表示活动i先于j，a[i，j]=0，表示活动i与j不存在先后关系。

（1）计算各顶点的入度

（2）找入度为零的点输出之，删除该点，且与该点关联各点的入度减1

（3）若所有顶点都输出完毕。

程序如下：

program tppv;
const maxn=100;
var
map:array[1..maxn,1..maxn] of byte;
into:array[1..maxn] of byte;
n,i,j,k:byte;
procere init;
var
i,j:integer;
begin
read(n);
for i:=1 to n do
for j:=1 to n do
begin
read(map[i,j]);
inc(into[j]);
end;
end;
begin
init;
for i:=1 to n do
begin
j:=1;
while (j<=n)and(into[j]<>0) do inc(j);
write(j,' ');
into[j]:=255;
for k:=1 to n do
if map[j,k]=1 then dec(into[k]);
end;
end.

3.3应用举例与练习

例：士兵排队问题：

有N个士兵（1<=N<=100),编号依次为1,2,...,N.队列训练时，指挥官要把士兵从高到矮排成一行，但指挥官只知道“1 比2 高，7 比 5高”这样的比较结果。

输入文件：第一行为数N（N〈=100）；表示士兵的个数。以下若干行每行两个数A，B 表示A高于B。

输出文件：给出一个合法的排队序列。

程序如下：

program tppv;
const maxn=100;
var
map:array[1..maxn,1..maxn] of byte;
into:array[1..maxn] of byte;
n,i,j,k:byte;
fp:text;
procere init;
var
i,j:integer;
begin
assign(fp,'tp.txt');
reset(fp);
readln(fp,n);
fillchar(map,sizeof(map),0);
fillchar(into,sizeof(into),0);
while not(seekeof(fp)) do
begin
readln(fp,i,j);
map[i,j]=1 ;
inc(into[j]);
end;
close(fp);
end;
begin
init;
for i:=1 to n do
begin
j:=1;
while (j<=n)and(into[j]<>0) do inc(j);
write(j,' ');
into[j]:=255;
for k:=1 to n do
if map[j,k]=1 then dec(into[k]);
end;
end.

练习：

Z语言问题：Z语言的基本字母也是26个，不妨用a到z表示，但先后顺序与英语不同。

现在按Z语言的顺序给出了N个单词，请依照这些单词给出一个可能的Z语言字母顺序。

输入文件：第一行一个数N（N<=100)表示单词的个数。

第二行到第N+1行，每行一个单词。

输出文件：仅一行，可能的字母顺序。

(图不好粘贴）

4. pso的拓扑结构

通过设计不同类型的拓扑来提高PSO算法的性能，也是一个活跃的研究方向。
既然是研究拓扑结构，一定会涉及到邻域的概念。邻域可以是静态的，也可以是动态确定的。邻域的确定有两种方式，一种为根据微粒的标志（或索引）来确定，与距离无关；而另一种为根据微粒之间的拓扑距离来确定。显然，按照拓扑距离动态确定邻域的计算量会比较大。
大多数研究针对静态拓扑来展开。Kennedy分析了各种各样的静态邻域结构以及它们对算法性能的影响，认为星形、环形和Von Neumann拓扑适用性最好，并宣称小邻域的PSO算法在复杂问题上性能较好，但是大邻域的PSO算法在简单问题上性能会更好。Kennedy还基于K均值聚类算法提出混合空间邻域和环形拓扑方法的另一个局部PSO算法版本，称为社会趋同法，不用每个微粒的经验而是用它所属空间聚类的共同经验来更新自己。Engelbrecht研究了基本的PSO算法定位并维持多个最优点的能力，发现全局邻域PSO（gBest PSO）算法对此根本无能为力，而局部邻域PSO（nBest PSO）算法则是效率很低。
Peram发展了一种基于适应值距离比的PSO算法（FDR-PSO），使用近邻的交互。在更新速度的每一维分量时，FDR-PSO算法选择一个其他微粒的nBest，该微粒应具有更高的适应值，并且与待更新的微粒距离更近。该算法在每一维速度更新中选取不同邻域微粒，比在所有速度维只选取一个邻域微粒更有效。Peer用不同的邻域拓扑来研究保证收敛PSO（GCPSO）算法的性能。Parsopoulos将全局版本和局部版本组合在一起，构建了一个统一微粒群算法（Unified ParticleSwarm Optimizer, UPSO）。与此有异曲同工之效的是Xu提出的扩展PSO算法，同时使用个体最优、全局最优以及邻域中的局部最优来更新速度。Mendes介绍了一种完全通知（Fully informed）的PSO算法，使用微粒的所有邻居信息来更新速度，每个微粒对其邻居的影响基于它的适应值大小和邻域大小进行加权。在此基础上，方峻发展出一种基于加权有向拓扑的的改进算法，体现微粒之间影响的不平衡性。
也有少部分研究工作是关于动态拓扑的。Suganthan使用了一个动态调整的邻域，微粒的邻域逐渐增大，直到包含所有的微粒为止。Hu研究了一种动态邻域，在每一代的性能空间中m个最近的微粒被选作新的邻居。Mohais研究了两种随机动态邻域拓扑。Binkley提出一种带影响范围的PSO算法，最优微粒对其余各微粒的影响能力取决于它们之间的距离。分层PSO算法使用基于种群中每个微粒的性能得到的动态树分层概念来定义邻域结构。
上述邻域拓扑均用于确定群体经验gBest，而Jian使用邻域拓扑来确定个体经验pBest。

5. 常用的内存管理方法有哪几种

常用的内存管理 方法 有哪几种?下面是我给大家收集整理的一些相关方法技巧，希望对大家有帮助!

传统的内存整理软件工作原理大概是：先申请一块“巨大内存”。因为物理内存几乎全被内存整理软件占用，因此Windows被迫把其他软件的内存数据转移到硬盘上的“虚拟内存交换文件”(PageFile)中，完成这一过程之后内存整理软件就会释放掉刚刚申请的内存，至此整理过程完成，可用物理内存显着增加。

大体上都是那么回事，就是通过辅助空间，重新安排内存内容 ....

但是其中使用的算法，效率是有很大的区别的 ～～ <script type="text/javascript"><!-- google_ad_client = "pub-4403405132739389"; google_ad_width = 250; google_ad_height = 250; google_ad_format = "250x250_as"; google_ad_type = "text"; //2007-10-22: 250*250 google_ad_channel = "7687946060"; google_ui_features = "rc:10"; //--> </script><script type="text/javascript" src=pagead2.googlesyndication/pagead/show_ads.js"> </script>

拓荒时代

国内的程序员大多是在 Java 语言中第一次感受到垃圾收集技术的巨大魅力的，许多人也因此把 Java 和垃圾收集看成了密不可分的整体。但事实上，垃圾收集技术早在 Java 语言问世前 30 多年就已经发展和成熟起来了， Java 语言所做的不过是把这项神奇的技术带到了广大程序员身边而已。

如果一定要为垃圾收集技术找一个孪生兄弟，那么， Lisp 语言才是当之无愧的人选。 1960 年前后诞生于 MIT 的 Lisp 语言是第一种高度依赖于动态内存分配技术的语言： Lisp 中几乎所有数据都以“表”的形式出现，而“表”所占用的空间则是在堆中动态分配得到的。 Lisp 语言先天就具有的动态内存管理特性要求 Lisp 语言的设计者必须解决堆中每一个内存块的自动释放问题(否则， Lisp 程序员就必然被程序中不计其数的 free 或 delete 语句淹没)，这直接导致了垃圾收集技术的诞生和发展——说句题外话，上大学时，一位老师曾告诉我们， Lisp 是对现代软件开发技术贡献最大的语言。我当时对这一说法不以为然：布满了圆括号，看上去像迷宫一样的 Lisp 语言怎么能比 C 语言或 Pascal 语言更伟大呢?不过现在，当我知道垃圾收集技术、数据结构技术、人工智能技术、并行处理技术、虚拟机技术、元数据技术以及程序员们耳熟能详的许多技术都起源于 Lisp 语言时，我特别想向那位老师当面道歉，并收回我当时的幼稚想法。

知道了 Lisp 语言与垃圾收集的密切关系，我们就不难理解，为什么垃圾收集技术的两位先驱者 J. McCarthy 和 M. L. Minsky 同时也是 Lisp 语言发展史上的重要人物了。 J. McCarthy 是 Lisp 之父，他在发明 Lisp 语言的同时也第一次完整地描述了垃圾收集的算法和实现方式; M. L. Minsky 则在发展 Lisp 语言的过程中成为了今天好几种主流垃圾收集算法的奠基人——和当时不少技术大师的经历相似， J. McCarthy 和 M. L. Minsky 在许多不同的技术领域里都取得了令人艳羡的成就。也许，在 1960 年代那个软件开发史上的拓荒时代里，思维敏捷、意志坚定的研究者更容易成为无所不能的西部硬汉吧。

在了解垃圾收集算法的起源之前，有必要先回顾一下内存分配的主要方式。我们知道，大多数主流的语言或运行环境都支持三种最基本的内存分配方式，它们分别是：

一、静态分配( Static Allocation )：静态变量和全局变量的分配形式。我们可以把静态分配的内存看成是家里的耐用家具。通常，它们无需释放和回收，因为没人会天天把大衣柜当作垃圾扔到窗外。

二、自动分配( Automatic Allocation )：在栈中为局部变量分配内存的方法。栈中的内存可以随着代码块退出时的出栈操作被自动释放。这类似于到家中串门的访客，天色一晚就要各回各家，除了个别不识时务者以外，我们一般没必要把客人捆在垃圾袋里扫地出门。

三、动态分配( Dynamic Allocation )：在堆中动态分配内存空间以存储数据的方式。堆中的内存块好像我们日常使用的餐巾纸，用过了就得扔到垃圾箱里，否则屋内就会满地狼藉。像我这样的懒人做梦都想有一台家用机器人跟在身边打扫卫生。在软件开发中，如果你懒得释放内存，那么你也需要一台类似的机器人——这其实就是一个由特定算法实现的垃圾收集器。

也就是说，下面提到的所有垃圾收集算法都是在程序运行过程中收集并清理废旧“餐巾纸”的算法，它们的操作对象既不是静态变量，也不是局部变量，而是堆中所有已分配内存块。

引用计数( Reference Counting )算法

1960 年以前，人们为胚胎中的 Lisp 语言设计垃圾收集机制时，第一个想到的算法是引用计数算法。拿餐巾纸的例子来说，这种算法的原理大致可以描述为：

午餐时，为了把脑子里突然跳出来的设计灵感记下来，我从餐巾纸袋中抽出一张餐巾纸，打算在上面画出系统架构的蓝图。按照“餐巾纸使用规约之引用计数版”的要求，画图之前，我必须先在餐巾纸的一角写上计数值 1 ，以表示我在使用这张餐巾纸。这时，如果你也想看看我画的蓝图，那你就要把餐巾纸上的计数值加 1 ，将它改为 2 ，这表明目前有 2 个人在同时使用这张餐巾纸(当然，我是不会允许你用这张餐巾纸来擦鼻涕的)。你看完后，必须把计数值减 1 ，表明你对该餐巾纸的使用已经结束。同样，当我将餐巾纸上的内容全部誊写到 笔记本 上之后，我也会自觉地把餐巾纸上的计数值减 1 。此时，不出意外的话，这张餐巾纸上的计数值应当是 0 ，它会被垃圾收集器——假设那是一个专门负责打扫卫生的机器人——捡起来扔到垃圾箱里，因为垃圾收集器的惟一使命就是找到所有计数值为 0 的餐巾纸并清理它们。

引用计数算法的优点和缺陷同样明显。这一算法在执行垃圾收集任务时速度较快，但算法对程序中每一次内存分配和指针操作提出了额外的要求(增加或减少内存块的引用计数)。更重要的是，引用计数算法无法正确释放循环引用的内存块，对此， D. Hillis 有一段风趣而精辟的论述：

一天，一个学生走到 Moon 面前说：“我知道如何设计一个更好的垃圾收集器了。我们必须记录指向每个结点的指针数目。” Moon 耐心地给这位学生讲了下面这个 故事 ：“一天，一个学生走到 Moon 面前说：‘我知道如何设计一个更好的垃圾收集器了……’”

D. Hillis 的故事和我们小时候常说的“从前有座山，山上有个庙，庙里有个老和尚”的故事有异曲同工之妙。这说明，单是使用引用计数算法还不足以解决垃圾收集中的所有问题。正因为如此，引用计数算法也常常被研究者们排除在狭义的垃圾收集算法之外。当然，作为一种最简单、最直观的解决方案，引用计数算法本身具有其不可替代的优越性。 1980 年代前后， D. P. Friedman ， D. S. Wise ， H. G. Baker 等人对引用计数算法进行了数次改进，这些改进使得引用计数算法及其变种(如延迟计数算法等)在简单的环境下，或是在一些综合了多种算法的现代垃圾收集系统中仍然可以一展身手。

标记-清除( Mark-Sweep )算法

第一种实用和完善的垃圾收集算法是 J. McCarthy 等人在 1960 年提出并成功地应用于 Lisp 语言的标记-清除算法。仍以餐巾纸为例，标记-清除算法的执行过程是这样的：

午餐过程中，餐厅里的所有人都根据自己的需要取用餐巾纸。当垃圾收集机器人想收集废旧餐巾纸的时候，它会让所有用餐的人先停下来，然后，依次询问餐厅里的每一个人：“你正在用餐巾纸吗?你用的是哪一张餐巾纸?”机器人根据每个人的回答将人们正在使用的餐巾纸画上记号。询问过程结束后，机器人在餐厅里寻找所有散落在餐桌上且没有记号的餐巾纸(这些显然都是用过的废旧餐巾纸)，把它们统统扔到垃圾箱里。

正如其名称所暗示的那样，标记-清除算法的执行过程分为“标记”和“清除”两大阶段。这种分步执行的思路奠定了现代垃圾收集算法的思想基础。与引用计数算法不同的是，标记-清除算法不需要运行环境监测每一次内存分配和指针操作，而只要在“标记”阶段中跟踪每一个指针变量的指向——用类似思路实现的垃圾收集器也常被后人统称为跟踪收集器( Tracing Collector )

伴随着 Lisp 语言的成功，标记-清除算法也在大多数早期的 Lisp 运行环境中大放异彩。尽管最初版本的标记-清除算法在今天看来还存在效率不高(标记和清除是两个相当耗时的过程)等诸多缺陷，但在后面的讨论中，我们可以看到，几乎所有现代垃圾收集算法都是标记-清除思想的延续，仅此一点， J. McCarthy 等人在垃圾收集技术方面的贡献就丝毫不亚于他们在 Lisp 语言上的成就了。

复制( Copying )算法

为了解决标记-清除算法在垃圾收集效率方面的缺陷， M. L. Minsky 于 1963 年发表了着名的论文“一种使用双存储区的 Lisp 语言垃圾收集器( A LISP Garbage Collector Algorithm Using Serial Secondary Storage )”。 M. L. Minsky 在该论文中描述的算法被人们称为复制算法，它也被 M. L. Minsky 本人成功地引入到了 Lisp 语言的一个实现版本中。

复制算法别出心裁地将堆空间一分为二，并使用简单的复制操作来完成垃圾收集工作，这个思路相当有趣。借用餐巾纸的比喻，我们可以这样理解 M. L. Minsky 的复制算法：

餐厅被垃圾收集机器人分成南区和北区两个大小完全相同的部分。午餐时，所有人都先在南区用餐(因为空间有限，用餐人数自然也将减少一半)，用餐时可以随意使用餐巾纸。当垃圾收集机器人认为有必要回收废旧餐巾纸时，它会要求所有用餐者以最快的速度从南区转移到北区，同时随身携带自己正在使用的餐巾纸。等所有人都转移到北区之后，垃圾收集机器人只要简单地把南区中所有散落的餐巾纸扔进垃圾箱就算完成任务了。下一次垃圾收集的工作过程也大致类似，惟一的不同只是人们的转移方向变成了从北区到南区。如此循环往复，每次垃圾收集都只需简单地转移(也就是复制)一次，垃圾收集速度无与伦比——当然，对于用餐者往返奔波于南北两区之间的辛劳，垃圾收集机器人是决不会流露出丝毫怜悯的。

M. L. Minsky 的发明绝对算得上一种奇思妙想。分区、复制的思路不仅大幅提高了垃圾收集的效率，而且也将原本繁纷复杂的内存分配算法变得前所未有地简明和扼要(既然每次内存回收都是对整个半区的回收，内存分配时也就不用考虑内存碎片等复杂情况，只要移动堆顶指针，按顺序分配内存就可以了)，这简直是个奇迹!不过，任何奇迹的出现都有一定的代价，在垃圾收集技术中，复制算法提高效率的代价是人为地将可用内存缩小了一半。实话实说，这个代价未免也太高了一些。

无论优缺点如何，复制算法在实践中都获得了可以与标记-清除算法相比拟的成功。除了 M. L. Minsky 本人在 Lisp 语言中的工作以外，从 1960 年代末到 1970 年代初， R. R. Fenichel 和 J. C. Yochelson 等人也相继在 Lisp 语言的不同实现中对复制算法进行了改进， S. Arnborg 更是成功地将复制算法应用到了 Simula 语言中。

至此，垃圾收集技术的三大传统算法——引用计数算法、标记-清除算法和复制算法——都已在 1960 年前后相继问世，三种算法各有所长，也都存在致命的缺陷。从 1960 年代后期开始，研究者的主要精力逐渐转向对这三种传统算法进行改进或整合，以扬长避短，适应程序设计语言和运行环境对垃圾收集的效率和实时性所提出的更高要求。

走向成熟

从 1970 年代开始，随着科学研究和应用实践的不断深入，人们逐渐意识到，一个理想的垃圾收集器不应在运行时导致应用程序的暂停，不应额外占用大量的内存空间和 CPU 资源，而三种传统的垃圾收集算法都无法满足这些要求。人们必须提出更新的算法或思路，以解决实践中碰到的诸多难题。当时，研究者的努力目标包括：

第一，提高垃圾收集的效率。使用标记-清除算法的垃圾收集器在工作时要消耗相当多的 CPU 资源。早期的 Lisp 运行环境收集内存垃圾的时间竟占到了系统总运行时间的 40% !——垃圾收集效率的低下直接造就了 Lisp 语言在执行速度方面的坏名声;直到今天，许多人还条件反射似地误以为所有 Lisp 程序都奇慢无比。

第二，减少垃圾收集时的内存占用。这一问题主要出现在复制算法中。尽管复制算法在效率上获得了质的突破，但牺牲一半内存空间的代价仍然是巨大的。在计算机发展的早期，在内存价格以 KB 计算的日子里，浪费客户的一半内存空间简直就是在变相敲诈或拦路打劫。

第三，寻找实时的垃圾收集算法。无论执行效率如何，三种传统的垃圾收集算法在执行垃圾收集任务时都必须打断程序的当前工作。这种因垃圾收集而造成的延时是许多程序，特别是执行关键任务的程序没有办法容忍的。如何对传统算法进行改进，以便实现一种在后台悄悄执行，不影响——或至少看上去不影响——当前进程的实时垃圾收集器，这显然是一件更具挑战性的工作。

研究者们探寻未知领域的决心和研究工作的进展速度同样令人惊奇：在 1970 年代到 1980 年代的短短十几年中，一大批在实用系统中表现优异的新算法和新思路脱颖而出。正是因为有了这些日趋成熟的垃圾收集算法，今天的我们才能在 Java 或 .NET 提供的运行环境中随心所欲地分配内存块，而不必担心空间释放时的风险。

标记-整理( Mark-Compact )算法

标记-整理算法是标记-清除算法和复制算法的有机结合。把标记-清除算法在内存占用上的优点和复制算法在执行效率上的特长综合起来，这是所有人都希望看到的结果。不过，两种垃圾收集算法的整合并不像 1 加 1 等于 2 那样简单，我们必须引入一些全新的思路。 1970 年前后， G. L. Steele ， C. J. Cheney 和 D. S. Wise 等研究者陆续找到了正确的方向，标记-整理算法的轮廓也逐渐清晰了起来：

在我们熟悉的餐厅里，这一次，垃圾收集机器人不再把餐厅分成两个南北区域了。需要执行垃圾收集任务时，机器人先执行标记-清除算法的第一个步骤，为所有使用中的餐巾纸画好标记，然后，机器人命令所有就餐者带上有标记的餐巾纸向餐厅的南面集中，同时把没有标记的废旧餐巾纸扔向餐厅北面。这样一来，机器人只消站在餐厅北面，怀抱垃圾箱，迎接扑面而来的废旧餐巾纸就行了。

实验表明，标记-整理算法的总体执行效率高于标记-清除算法，又不像复制算法那样需要牺牲一半的存储空间，这显然是一种非常理想的结果。在许多现代的垃圾收集器中，人们都使用了标记-整理算法或其改进版本。

增量收集( Incremental Collecting )算法

对实时垃圾收集算法的研究直接导致了增量收集算法的诞生。

最初，人们关于实时垃圾收集的想法是这样的：为了进行实时的垃圾收集，可以设计一个多进程的运行环境，比如用一个进程执行垃圾收集工作，另一个进程执行程序代码。这样一来，垃圾收集工作看上去就仿佛是在后台悄悄完成的，不会打断程序代码的运行。

在收集餐巾纸的例子中，这一思路可以被理解为：垃圾收集机器人在人们用餐的同时寻找废弃的餐巾纸并将它们扔到垃圾箱里。这个看似简单的思路会在设计和实现时碰上进程间冲突的难题。比如说，如果垃圾收集进程包括标记和清除两个工作阶段，那么，垃圾收集器在第一阶段中辛辛苦苦标记出的结果很可能被另一个进程中的内存操作代码修改得面目全非，以至于第二阶段的工作没有办法开展。

M. L. Minsky 和 D. E. Knuth 对实时垃圾收集过程中的技术难点进行了早期的研究， G. L. Steele 于 1975 年发表了题为“多进程整理的垃圾收集( Multiprocessing compactifying garbage collection )”的论文，描述了一种被后人称为“ Minsky-Knuth-Steele 算法”的实时垃圾收集算法。 E. W. Dijkstra ， L. Lamport ， R. R. Fenichel 和 J. C. Yochelson 等人也相继在此领域做出了各自的贡献。 1978 年， H. G. Baker 发表了“串行计算机上的实时表处理技术( List Processing in Real Time on a Serial Computer )”一文，系统阐述了多进程环境下用于垃圾收集的增量收集算法。

增量收集算法的基础仍是传统的标记-清除和复制算法。增量收集算法通过对进程间冲突的妥善处理，允许垃圾收集进程以分阶段的方式完成标记、清理或复制工作。详细分析各种增量收集算法的内部机理是一件相当繁琐的事情，在这里，读者们需要了解的仅仅是： H. G. Baker 等人的努力已经将实时垃圾收集的梦想变成了现实，我们再也不用为垃圾收集打断程序的运行而烦恼了。

分代收集( Generational Collecting )算法

和大多数软件开发技术一样，统计学原理总能在技术发展的过程中起到强力催化剂的作用。 1980 年前后，善于在研究中使用统计分析知识的技术人员发现，大多数内存块的生存周期都比较短，垃圾收集器应当把更多的精力放在检查和清理新分配的内存块上。这个发现对于垃圾收集技术的价值可以用餐巾纸的例子概括如下：

如果垃圾收集机器人足够聪明，事先摸清了餐厅里每个人在用餐时使用餐巾纸的习惯——比如有些人喜欢在用餐前后各用掉一张餐巾纸，有的人喜欢自始至终攥着一张餐巾纸不放，有的人则每打一个喷嚏就用去一张餐巾纸——机器人就可以制定出更完善的餐巾纸回收计划，并总是在人们刚扔掉餐巾纸没多久就把垃圾捡走。这种基于统计学原理的做法当然可以让餐厅的整洁度成倍提高。

D. E. Knuth ， T. Knight ， G. Sussman 和 R. Stallman 等人对内存垃圾的分类处理做了最早的研究。 1983 年， H. Lieberman 和 C. Hewitt 发表了题为“基于对象寿命的一种实时垃圾收集器( A real-time garbage collector based on the lifetimes of objects )”的论文。这篇着名的论文标志着分代收集算法的正式诞生。此后，在 H. G. Baker ， R. L. Hudson ， J. E. B. Moss 等人的共同努力下，分代收集算法逐渐成为了垃圾收集领域里的主流技术。

分代收集算法通常将堆中的内存块按寿命分为两类，年老的和年轻的。垃圾收集器使用不同的收集算法或收集策略，分别处理这两类内存块，并特别地把主要工作时间花在处理年轻的内存块上。分代收集算法使垃圾收集器在有限的资源条件下，可以更为有效地工作——这种效率上的提高在今天的 Java 虚拟机中得到了最好的证明。

应用浪潮

Lisp 是垃圾收集技术的第一个受益者，但显然不是最后一个。在 Lisp 语言之后，许许多多传统的、现代的、后现代的语言已经把垃圾收集技术拉入了自己的怀抱。随便举几个例子吧：诞生于 1964 年的 Simula 语言， 1969 年的 Smalltalk 语言， 1970 年的 Prolog 语言， 1973 年的 ML 语言， 1975 年的 Scheme 语言， 1983 年的 Mola-3 语言， 1986 年的 Eiffel 语言， 1987 年的 Haskell 语言……它们都先后使用了自动垃圾收集技术。当然，每一种语言使用的垃圾收集算法可能不尽相同，大多数语言和运行环境甚至同时使用了多种垃圾收集算法。但无论怎样，这些实例都说明，垃圾收集技术从诞生的那一天起就不是一种曲高和寡的“学院派”技术。

对于我们熟悉的 C 和 C++ 语言，垃圾收集技术一样可以发挥巨大的功效。正如我们在学校中就已经知道的那样， C 和 C++ 语言本身并没有提供垃圾收集机制，但这并不妨碍我们在程序中使用具有垃圾收集功能的函数库或类库。例如，早在 1988 年， H. J. Boehm 和 A. J. Demers 就成功地实现了一种使用保守垃圾收集算法( Conservative GC Algorithmic )的函数库。我们可以在 C 语言或 C++ 语言中使用该函数库完成自动垃圾收集功能，必要时，甚至还可以让传统的 C/C++ 代码与使用自动垃圾收集功能的 C/C++ 代码在一个程序里协同工作。

1995 年诞生的 Java 语言在一夜之间将垃圾收集技术变成了软件开发领域里最为流行的技术之一。从某种角度说，我们很难分清究竟是 Java 从垃圾收集中受益，还是垃圾收集技术本身借 Java 的普及而扬名。值得注意的是，不同版本的 Java 虚拟机使用的垃圾收集机制并不完全相同， Java 虚拟机其实也经过了一个从简单到复杂的发展过程。在 Java 虚拟机的 1.4.1 版中，人们可以体验到的垃圾收集算法就包括分代收集、复制收集、增量收集、标记-整理、并行复制( Parallel Copying )、并行清除( Parallel Scavenging )、并发( Concurrent )收集等许多种， Java 程序运行速度的不断提升在很大程度上应该归功于垃圾收集技术的发展与完善。

尽管历史上已经有许多包含垃圾收集技术的应用平台和 操作系统 出现，但 Microsoft .NET 却是第一种真正实用化的、包含了垃圾收集机制的通用语言运行环境。事实上， .NET 平台上的所有语言，包括 C# 、 Visual Basic .NET 、 Visual C++ .NET 、 J# 等等，都可以通过几乎完全相同的方式使用 .NET 平台提供的垃圾收集机制。我们似乎可以断言， .NET 是垃圾收集技术在应用领域里的一次重大变革，它使垃圾收集技术从一种单纯的技术变成了应用环境乃至操作系统中的一种内在 文化 。这种变革对未来软件开发技术的影响力也许要远远超过 .NET 平台本身的商业价值。

大势所趋

今天，致力于垃圾收集技术研究的人们仍在不懈努力，他们的研究方向包括分布式系统的垃圾收集、复杂事务环境下的垃圾收集、数据库等特定系统的垃圾收集等等。

但在程序员中间，仍有不少人对垃圾收集技术不屑一顾，他们宁愿相信自己逐行编写的 free 或 delete 命令，也不愿把垃圾收集的重任交给那些在他们看来既蠢又笨的垃圾收集器。

我个人认为，垃圾收集技术的普及是大势所趋，这就像生活会越来越好一样毋庸置疑。今天的程序员也许会因为垃圾收集器要占用一定的 CPU 资源而对其望而却步，但二十多年前的程序员还曾因为高级语言速度太慢而坚持用机器语言写程序呢!在硬件速度日新月异的今天，我们是要吝惜那一点儿时间损耗而踟躇不前，还是该坚定不移地站在代码和运行环境的净化剂——垃圾收集的一边呢?

6. 数据中心网络中常用的拓扑结构---Fattree

姓名：姜国勇

学号：20011210153

转自：https://blog.csdn.net/bryanting/article/details/80000864

【嵌牛导读】数据中心是全球协作的特定设备网络，用来在网络基础设施上传递、加速、展示、计算、存储数据信息。

    在今后的发展中，数据中心也将会成为企业竞争的资产，商业模式也会因此发生改变。随着数据中心应用的广泛化，人工智能、网络安全等也相继出现，更多的用户都被带到了网络和手机的应用中。随着计算机和数据量的增多，人们也可以通过不断学习积累提升自身的能力，是迈向信息化时代的重要标志。

   其中，fat-tree模型为大多数数据中心网络构建常用的拓扑结构，在稳定性方面有着显着的优势。

【嵌牛鼻子】FatTree拓扑结构  数据中心网络

【嵌牛正文】

       FatTree拓扑结构是由MIT的Fares等人在改进传统树形结构性能的基础上提出的，属于switch-only型拓扑。

        整个拓扑网络分为三个层次：自上而下分别为边缘层（edge）、汇聚层（aggregate）和核心层（core），其中汇聚层交换机与边缘层交换机构成一个pod，交换设备均采用商用交换设备。

   滑李慧     FatTree构建拓扑规则如下：FatTree拓扑中包含的Pod数目为  ，每一个pod连接的sever数目为 ，每一个pod内的边缘交换机及聚合交换机数量均为 ，核心交换机数量为 ，网络中每一个交换机的端口数量为 ，网络所能支持的服务器总数为 。

        FatTree结构采用水平扩展的方式，当拓扑中所包含的pod数目增加，交换机的端口数目增加时，FatTree拓扑能够支持更多的服务器，满足数据中心的扩展需求，如k=48k=48时，FatTree能够支持的服务器数目为27648。

        FatTree结构通过在核心层多条链路实现负载的及时处理，避免网络热点；通过在pod内合理分流，避免过载问题。

        FatTree对分带宽随着网络规模的扩展而增大，因此能够为数据中心提供高吞吐传输服务；不同pod之间的服务器间通信，源、目的节点之间具有多条并行路径，因此网络的容错性能良好，一般不会出现单点故障；信答采用商用设备取代高性能交换设备，大幅度降低网络设备开销；网络直径小，能够保证视频、在线会与等服务对网络实时性的要求；拓扑结构规则、对称，利于网络布线及自动化配置、优化升级等。

        Fat-Tree结构也存在一定的缺陷：Fat-Tree结构的扩展规模在理论上受限于核心交换机的端口数目，不利于数据中心的长期发展要求；对于Pod内部，Fat-Tree容错性能差，对底层交换设备故障非常敏感，当底层交换设备故障时，难以保证服务质量；拓扑结构的特点决定了网络不能很好的支持one-to-all及all-to-all网络通信模式，不利于部署MapRece、Dryad等现代高性能应用；网络中交换机与服务器的比值较大，在一定程度上使得网络设备成本依然很高，不利于企业的经济扰巧发展。

7. 传统优化算法和现代优化算法包括哪些.区别是什么

1. 传统优化算法一般是针对结构化的问题，有较为明确的问题和条件描述，如线性规划，二次规划，整数规划，混合规划，带约束和不带约束条件等，即有清晰的结构信息；而智能优化算法一般针对的是较为普适的问题描述，普遍比较缺乏结构信息。

2. 传统优化算法不少都属于凸优化范畴，有唯一明确的全局最优点；而智能优化算法针对的绝大多数是多极值问题，如何防止陷入局部最优而尽可能找到全局最优是采纳智能优化算法的根本原因：对于单极值问题，传统算法大部分时候已足够好，而智能算法没有任何优势；对多极值问题，智能优化算法通过其有效设计可以在跳出局部最优和收敛到一个点之间有个较好的平衡，从而实现找到全局最优点，但有的时候局部最优也是可接受的，所以传统算法也有很大应用空间和针对特殊结构的改进可能。

3. 传统优化算法一般是确定性算法，有固定的结构和参数，计算复杂度和收敛性可做理论分析；智能优化算法大多属于启发性算法，能定性分析却难定量证明，且大多数算法基于随机特性，其收敛性一般是概率意义上的，实际性能不可控，往往收敛速度也比较慢，计算复杂度较高。

8. 拓扑排序算法实现

#define MAXV 30
#define OK 1
#define ERROR 0
typedef char VertexType;
typedef int status;

typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;

typedef struct VNode{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAXV ];

typedef struct{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;

int LocateVex(ALGraph G,char m);
status Creat_Graph1(ALGraph &G);
int dfs_topsort(ALGraph g,int n);//拓扑排序算法

void dfs(ALGraph g,int v,int&flag);//深度优先搜索
void Menuselect();
头文件

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<iostream.h>
#include"head.h"

int visited[MAXV];
int finished[MAXV];

int dfs_topsort(ALGraph g,int n)
{
int flag=1,i;
for(i=0;i<n;i++) //置初值
{
visited[i]=0;
finished[i]=1;
}
i=0; //从编号为0的顶点开始遍历
while(flag&&i<n)
{
if(visited[i]==0)
{ i++;
dfs(g,i,flag);}

}
return flag;
}

void dfs(ALGraph g,int v,int&flag)
{
ArcNode *p;
printf("%d\n",v);
finished[v]=0;
visited[v]=0;
p=g.vertices[v]. firstarc; //找顶点V的第一条弧
while(p!=NULL)
{

if(visited[p->adjvex]==0)
{
dfs(g,p->adjvex,flag);
finished[p->adjvex ]=1;
}
p=p->nextarc ;
}
}

int LocateVex(ALGraph G,char m){
int i;
for(i=0;i<G.vexnum;i++)
if(G.vertices[i].data==m)return i;
return ERROR;
}

status Creat_Graph1(ALGraph &G){
int i,j,r;char m,n;ArcNode *p;
printf("请输入顶点数：");
scanf("%d",&G.vexnum);
printf("请输入边数：");
scanf("%d",&G.arcnum);
printf("请输入图的所有顶点：");
for(i=0;i<G.vexnum;i++)
{cin>裂笑>肆或含G.vertices[i].data;G.vertices[i].firstarc=NULL;}
printf("请输入图的所有边，如A->B边记团孙为AB，：\n");
for(r=0;r<G.arcnum;r++){
cin>>m;cin>>n;
i=LocateVex(G,m);j=LocateVex(G,n);

p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
p->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
}
return OK;
}

void Menuselect(){
int done=1,select,i;
ALGraph g;
printf("please input select number");
while(done){
printf("请输入操作码：");
scanf("%d",&select);
switch(select){
case 1:
if(Creat_Graph1(g))printf("OK");
printf("\n\n");
break;

case 2:
dfs_topsort( g,g.vexnum);
printf("\n\n");
break;
case 3:
done=0;
break;
default:printf("输入的操作码错误\n\n");
}
}
}
实现文件

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<iostream.h>
#include"head.h"
void main()
{

printf("图的拓扑排序");

Menuselect();

}
主文件

9. BP算法及其改进

传统的BP算法及其改进算法的一个很大缺点是：由于其误差目标函数对于待学习的连接权值来说非凸的，存在局部最小点，对网络进行训练时，这些算法的权值一旦落入权值空间的局部最小点就很难跳出，因而无法达到全局最小点(即最优点)而使得网络训练失败。针对这些缺陷，根据凸函数及其共轭的性质，利用Fenchel不等式，使用约束优化理论中的罚函数方法构造出了带有惩罚项的新误差目标函数。

用新的目标函数对前馈神经网络进行优化训练时，隐层输出也作为被优化变量。这个目标函数的主要特点有：
1.固定隐层输出，该目标函数对连接权值来说是凸的；固定连接权值，对隐层输出来说是凸的。这样在对连接权值和隐层输出进行交替优化时，它们所面对的目标函数都是凸函数，不存在局部最小的问题，算法对于初始权值的敏感性降低；
2.由于惩罚因子是逐渐增大的，使得权值的搜索空间变得比较大，从而对于大规模的网络也能够训练，在一定程度上降低了训练过程陷入局部最小的可能性。

这些特性能够在很大程度上有效地克服以往前馈网络的训练算法易于陷入局部最小而使网络训练失败的重大缺陷，也为利用凸优化理论研究前馈神经网络的学习算法开创了一个新思路。在网络训练时，可以对连接权值和隐层输出进行交替优化。把这种新算法应用到前馈神经网络训练学习中，在学习速度、泛化能力、网络训练成功率等多方面均优于传统训练算法，如经典的BP算法。数值试验也表明了这一新算法的有效性。

本文通过典型的BP算法与新算法的比较，得到了二者之间相互关系的初步结论。从理论上证明了当惩罚因子趋于正无穷大时新算法就是BP算法，并且用数值试验说明了惩罚因子在网络训练算法中的作用和意义。对于三层前馈神经网络来说，惩罚因子较小时，隐层神经元局部梯度的可变范围大，有利于连接权值的更新；惩罚因子较大时，隐层神经元局部梯度的可变范围小，不利于连接权值的更新，但能提高网络训练精度。这说明了在网络训练过程中惩罚因子为何从小到大变化的原因,也说明了新算法的可行性而BP算法则时有无法更新连接权值的重大缺陷。

矿体预测在矿床地质中占有重要地位，由于输入样本量大，用以往前馈网络算法进行矿体预测效果不佳。本文把前馈网络新算法应用到矿体预测中，取得了良好的预期效果。

本文最后指出了新算法的优点，并指出了有待改进的地方。

关键词：前馈神经网络，凸优化理论，训练算法，矿体预测，应用

Feed forward Neural Networks Training Algorithm Based on Convex Optimization and Its Application in Deposit Forcasting
JIA Wen-chen (Computer Application)
Directed by YE Shi-wei

Abstract

The paper studies primarily the application of convex optimization theory and algorithm for feed forward neural networks’ training and convergence performance.

It reviews the history of feed forward neural networks, points out that the training of feed forward neural networks is essentially a non-linear problem and introces BP algorithm, its advantages as well as disadvantages and previous improvements for it. One of the big disadvantages of BP algorithm and its improvement algorithms is: because its error target function is non-convex in the weight values between neurons in different layers and exists local minimum point, thus, if the weight values enter local minimum point in weight values space when network is trained, it is difficult to skip local minimum point and reach the global minimum point (i.e. the most optimal point).If this happening, the training of networks will be unsuccessful. To overcome these essential disadvantages, the paper constructs a new error target function including restriction item according to convex function, Fenchel inequality in the conjugate of convex function and punishment function method in restriction optimization theory.
When feed forward neural networks based on the new target function is being trained, hidden layers’ outputs are seen as optimization variables. The main characteristics of the new target function are as follows:

1.With fixed hidden layers’ outputs, the new target function is convex in connecting weight variables; with fixed connecting weight values, the new target function is convex in hidden layers’ outputs. Thus, when connecting weight values and hidden layers’ outputs are optimized alternately, the new target function is convex in them, doesn’t exist local minimum point, and the algorithm’s sensitiveness is reced for original weight values .
2.Because the punishment factor is increased graally, weight values ’ searching space gets much bigger, so big networks can be trained and the possibility of entering local minimum point can be reced to a certain extent in network training process.

Using these characteristics can overcome efficiently in the former feed forward neural networks’ training algorithms the big disadvantage that networks training enters local minimum point easily. This creats a new idea for feed forward neural networks’ learning algorithms by using convex optimization theory .In networks training, connecting weight variables and hidden layer outputs can be optimized alternately. The new algorithm is much better than traditional algorithms for feed forward neural networks. The numerical experiments show that the new algorithm is successful.

By comparing the new algorithm with the traditional ones, a primary conclusion of their relationship is reached. It is proved theoretically that when the punishment factor nears infinity, the new algorithm is BP algorithm yet. The meaning and function of the punishment factor are also explained by numerical experiments. For three-layer feed forward neural networks, when the punishment factor is smaller, hidden layer outputs’ variable range is bigger and this is in favor to updating of the connecting weights values, when the punishment factor is bigger, hidden layer outputs’ variable range is smaller and this is not in favor to updating of the connecting weights values but it can improve precision of networks. This explains the reason that the punishment factor should be increased graally in networks training process. It also explains feasibility of the new algorithm and BP algorithm’s disadvantage that connecting weigh values can not be updated sometimes.

Deposit forecasting is very important in deposit geology. The previous algorithms’ effect is not good in deposit forecasting because of much more input samples. The paper applies the new algorithm to deposit forecasting and expectant result is reached.
The paper points out the new algorithm’s strongpoint as well as to-be-improved places in the end.

Keywords: feed forward neural networks, convex optimization theory, training algorithm, deposit forecasting, application

传统的BP算法及其改进算法的一个很大缺点是：由于其误差目标函数对于待学习的连接权值来说非凸的，存在局部最小点，对网络进行训练时，这些算法的权值一旦落入权值空间的局部最小点就很难跳出，因而无法达到全局最小点(即最优点)而使得网络训练失败。针对这些缺陷，根据凸函数及其共轭的性质，利用Fenchel不等式，使用约束优化理论中的罚函数方法构造出了带有惩罚项的新误差目标函数。

用新的目标函数对前馈神经网络进行优化训练时，隐层输出也作为被优化变量。这个目标函数的主要特点有：
1.固定隐层输出，该目标函数对连接权值来说是凸的；固定连接权值，对隐层输出来说是凸的。这样在对连接权值和隐层输出进行交替优化时，它们所面对的目标函数都是凸函数，不存在局部最小的问题，算法对于初始权值的敏感性降低；
2.由于惩罚因子是逐渐增大的，使得权值的搜索空间变得比较大，从而对于大规模的网络也能够训练，在一定程度上降低了训练过程陷入局部最小的可能性。

这些特性能够在很大程度上有效地克服以往前馈网络的训练算法易于陷入局部最小而使网络训练失败的重大缺陷，也为利用凸优化理论研究前馈神经网络的学习算法开创了一个新思路。在网络训练时，可以对连接权值和隐层输出进行交替优化。把这种新算法应用到前馈神经网络训练学习中，在学习速度、泛化能力、网络训练成功率等多方面均优于传统训练算法，如经典的BP算法。数值试验也表明了这一新算法的有效性。

本文通过典型的BP算法与新算法的比较，得到了二者之间相互关系的初步结论。从理论上证明了当惩罚因子趋于正无穷大时新算法就是BP算法，并且用数值试验说明了惩罚因子在网络训练算法中的作用和意义。对于三层前馈神经网络来说，惩罚因子较小时，隐层神经元局部梯度的可变范围大，有利于连接权值的更新；惩罚因子较大时，隐层神经元局部梯度的可变范围小，不利于连接权值的更新，但能提高网络训练精度。这说明了在网络训练过程中惩罚因子为何从小到大变化的原因,也说明了新算法的可行性而BP算法则时有无法更新连接权值的重大缺陷。

矿体预测在矿床地质中占有重要地位，由于输入样本量大，用以往前馈网络算法进行矿体预测效果不佳。本文把前馈网络新算法应用到矿体预测中，取得了良好的预期效果。

本文最后指出了新算法的优点，并指出了有待改进的地方。

关键词：前馈神经网络，凸优化理论，训练算法，矿体预测，应用

Feed forward Neural Networks Training Algorithm Based on Convex Optimization and Its Application in Deposit Forcasting
JIA Wen-chen (Computer Application)
Directed by YE Shi-wei

Abstract

The paper studies primarily the application of convex optimization theory and algorithm for feed forward neural networks’ training and convergence performance.

It reviews the history of feed forward neural networks, points out that the training of feed forward neural networks is essentially a non-linear problem and introces BP algorithm, its advantages as well as disadvantages and previous improvements for it. One of the big disadvantages of BP algorithm and its improvement algorithms is: because its error target function is non-convex in the weight values between neurons in different layers and exists local minimum point, thus, if the weight values enter local minimum point in weight values space when network is trained, it is difficult to skip local minimum point and reach the global minimum point (i.e. the most optimal point).If this happening, the training of networks will be unsuccessful. To overcome these essential disadvantages, the paper constructs a new error target function including restriction item according to convex function, Fenchel inequality in the conjugate of convex function and punishment function method in restriction optimization theory.
When feed forward neural networks based on the new target function is being trained, hidden layers’ outputs are seen as optimization variables. The main characteristics of the new target function are as follows:

1.With fixed hidden layers’ outputs, the new target function is convex in connecting weight variables; with fixed connecting weight values, the new target function is convex in hidden layers’ outputs. Thus, when connecting weight values and hidden layers’ outputs are optimized alternately, the new target function is convex in them, doesn’t exist local minimum point, and the algorithm’s sensitiveness is reced for original weight values .
2.Because the punishment factor is increased graally, weight values ’ searching space gets much bigger, so big networks can be trained and the possibility of entering local minimum point can be reced to a certain extent in network training process.

Using these characteristics can overcome efficiently in the former feed forward neural networks’ training algorithms the big disadvantage that networks training enters local minimum point easily. This creats a new idea for feed forward neural networks’ learning algorithms by using convex optimization theory .In networks training, connecting weight variables and hidden layer outputs can be optimized alternately. The new algorithm is much better than traditional algorithms for feed forward neural networks. The numerical experiments show that the new algorithm is successful.

By comparing the new algorithm with the traditional ones, a primary conclusion of their relationship is reached. It is proved theoretically that when the punishment factor nears infinity, the new algorithm is BP algorithm yet. The meaning and function of the punishment factor are also explained by numerical experiments. For three-layer feed forward neural networks, when the punishment factor is smaller, hidden layer outputs’ variable range is bigger and this is in favor to updating of the connecting weights values, when the punishment factor is bigger, hidden layer outputs’ variable range is smaller and this is not in favor to updating of the connecting weights values but it can improve precision of networks. This explains the reason that the punishment factor should be increased graally in networks training process. It also explains feasibility of the new algorithm and BP algorithm’s disadvantage that connecting weigh values can not be updated sometimes.

Deposit forecasting is very important in deposit geology. The previous algorithms’ effect is not good in deposit forecasting because of much more input samples. The paper applies the new algorithm to deposit forecasting and expectant result is reached.
The paper points out the new algorithm’s strongpoint as well as to-be-improved places in the end.

Keywords: feed forward neural networks, convex optimization theory, training algorithm, deposit forecasting, application

BP算法及其改进

2.1 BP算法步骤

1°随机抽取初始权值ω0；

2°输入学习样本对（Xp,Yp），学习速率η，误差水平ε；

3°依次计算各层结点输出opi,opj,opk；

4°修正权值ωk+1=ωk+ηpk,其中pk=,ωk为第k次迭代权变量；

5°若误差E<ε停止，否则转3°。

2.2 最优步长ηk的确定

在上面的算法中，学习速率η实质上是一个沿负梯度方向的步长因子，在每一次迭代中如何确定一个最优步长ηk，使其误差值下降最快，则是典型的一维搜索问题，即E(ωk+ηkpk)=(ωk+ηpk)。令Φ(η)=E(ωk+ηpk)，则Φ′(η)=dE(ωk+ηpk)/dη=E(ωk+ηpk)Tpk。若ηk为(η)的极小值点，则Φ′(ηk)=0，即E(ωk+ηpk)Tpk=-pTk+1pk=0。确定ηk的算法步骤如下

1°给定η0=0,h=0.01,ε0=0.00001；

2°计算Φ′(η0),若Φ′(η0)=0,则令ηk=η0，停止计算；

3°令h=2h, η1=η0+h；

4°计算Φ′(η1)，若Φ′(η1)=0，则令ηk=η1，停止计算；

若Φ′(η1)>0，则令a=η0,b=η1；若Φ′(η1)<0，则令η0=η1，转3°；

5°计算Φ′(a)，若Φ′(a)=0，则ηk=a，停止计算；

6°计算Φ′(b)，若Φ′(b)=0，则ηk=b，停止计算；

7°计算Φ′(a+b/2),若Φ′(a+b/2)=0，则ηk=a+b/2，停止计算；

若Φ′(a+b/2)<0,则令a=a+b/2;若Φ′(a+b/2)>0，则令b=a+b/2

8°若｜a-b｜<ε0，则令，ηk=a+b/2,停止计算，否则转7°。

2.3 改进BP算法的特点分析

在上述改进的BP算法中，对学习速率η的选取不再由用户自己确定，而是在每次迭代过程中让计算机自动寻找最优步长ηk。而确定ηk的算法中，首先给定η0=0，由定义Φ(η)=E(ωk+ηpk)知，Φ′(η)=dE(ωk+ηpk)/dη=E(ωk+ηpk)Tpk，即Φ′(η0)=-pTkpk≤0。若Φ′(η0)=0，则表明此时下降方向pk为零向量，也即已达到局部极值点，否则必有Φ′(η0)<0，而对于一维函数Φ(η)的性质可知，Φ′(η0)<0则在η0=0的局部范围内函数为减函数。故在每一次迭代过程中给η0赋初值0是合理的。

改进后的BP算法与原BP算法相比有两处变化，即步骤2°中不需给定学习速率η的值；另外在每一次修正权值之前，即步骤4°前已计算出最优步长ηk。