资源描述
矩阵乘积可换的条件及应用数计学院 刘艳萍摘 要：矩阵的乘法运算一般不满足交换律，但在特殊的条件下可交换。本文从可交换矩阵和相关定义出发，对可交换矩阵做了深入的探讨，得到了矩阵可交换的一些条件和可交换矩阵的部分性质，并且介绍可交换矩阵的应用。关键词：矩阵乘法；可交换条件；应用 Interchangeable Conditions of the product of matricesand Its ApplicationsLiu Yanping(College of Mathematics and Computer Science, Guangxi University for Nationalities, Nanning 530006)Abstract: Generally the arithmetic of the matrix multiplication unconformity commutative law, but under special conditions they are interchangeable. In this paper, the interchangeable matrix is discussed, some conditions of the matrix exchange and part of the property of the interchangeable matrix are obtained, and the applications of the interchangeable matrix are introduced also. All of these are discussed from the concept of interchangeable matrix and related definitions. Key word: product of matrices; Interchangeable conditions; application1 引言及定义在高等代数学习中，矩阵是一个重要内容，由矩阵的理论可知，矩阵的乘法不同于复数的乘法，矩阵的乘法运算一般不满足交换律，即对两个方阵，在一般情形下。但在某些特殊情况下，矩阵的乘法也满足交换律，这时我们称是可交换矩阵。可交换矩阵有着许多特殊性质和作用。本文从可交换矩阵定义及相关定义出发，探讨矩阵可交换的一些条件和可交换矩阵的部分性质，并介绍可交换矩阵的一些应用。为研究矩阵可交换条件，我们先给出下列定义1。定义1 若同阶方阵有，则称方阵与为可交换矩阵.定义2 阶方阵中若元素满足，称为阶对角阵，记作.定义3 若阶方阵满足，其中为阶单位阵，则称为阶正交矩阵.用表示的转置矩阵；表示的伴随矩阵2。2 矩阵乘积可交换的条件及性质2.1 矩阵乘积可交换的条件定理1 设是的伴随矩阵，则与乘积可交换.证明 由即知.定理2 （1）设，其中,为非零实数，则,可交换；（2）设，其中为正整数，为非零实数，则,可交换.证明 （1）由可得，即，得，于是，所以.（2）由得，故，于是，从而.定理33 设, 均是阶可逆矩阵, 若对任意实数，均有，其中为 阶单位矩阵，则,可交换.定理4 设都是阶矩阵，则下列均是可交换的充要条件：(1) ；(2) ； (3) ；(4) .证明 (1) 由及即得.(2) 由 可证得；(3) 因，两端分别取它们的转置，得，又，故.由矩阵运算性质及已知条件，即得，两端分别取它们的转置，得.(4) 分别由，两边取伴随可证得.定理5 （1）设均为阶(反)对称矩阵，则可交换的充要条件是为对称矩阵；（2）设为阶对称阵，为阶反对称阵，可交换的充要条件是为反对称阵。证明 （1） 若均为阶对称矩阵，则 因 且，故，即为对称阵。 因又，故，即为可交换矩阵。 若均为反对称矩阵，则因且，故，即为对称阵。因又，故，即为可交换矩阵。（2）因，故，即为反对称阵。 因为反对称阵, ，又，故，即可交换。定理6 设均为对称正定矩阵，则可交换的充要条件是为对称正定矩阵.证明 充分性显然. 下面证明必要性。因为对称正定矩阵，故有可逆矩阵，使，于是，所以为对称正定矩阵，其特征值全为正数。而与相似，从而 的特征值也全为正数，因此为对称正定矩阵。定理7 设均为阶矩阵，若满足，则可交换的充要条件是.证明 因，故即. 由于，即,分别用左乘,右乘式的两边，得到，即.定理8 设是阶方阵，则与任一阶矩阵可换的充要条件是（数量矩阵）.证明 令是第行，第列处的元素为，其余元素为的阶方阵，因与任一阶矩阵可换，所以与所有可换，又(列)所以由的第行除外其余元素全为,，即除外，其余元素全为，故. 设，则对任意阶矩阵，有.定理9 设矩阵，其中当时，则可交换的充要条件是为对角矩阵.定理10 设为准对角矩阵，其中当时， ，是阶单位矩阵，则可交换的充要条件是为准对角矩阵.2.2 乘积可交换矩阵的性质性质1 设均为阶可交换矩阵，则有(1),其中都是正整数；(2) 对任意正整数， (矩阵二项式定理)；(3) 平方差公式：；(4) 完全平方和（差）公式：；(5) 矩阵积的乘幂公式：（是正整数）.证明 （1）先证明对任意正整数，有，对作数学归纳法 当时，由已知条件，即当时结论成立；假设当时结论成立，即，则当时， ，故当时结论也成立，由归纳法原理，对一切正整数，有；再证明， 对作数学归纳法. 当时，由上面结论知，即当时结论成立；假设当时结论成立，即，则当时，故当时结论也成立；由归纳法原理，对一切正整数，有 .(2) 对作数学归纳法.当时 当时，由，有即当时结论成立；假设当时结论成立，即 ，当时， .（倒数第三式到第二式利用了组合的性质：，及，）即当时结论也成立。从而由归纳法原理，对任意正整数，有= .(3)(5) 较明显，证明从略.性质24 设是阶复矩阵，则存在一个阶可逆矩阵，使得与同为上三角矩阵.证明 对的阶数作数学归纳法。当时，结论显然成立。假设结论对于阶矩阵也成立。当的阶数为时，由于，至少有一个公共的特征向量设将扩充为的一组基(均为列向量). 设 (1) (2)由得于是，由归纳法假设，存在阶可逆矩阵使得 ，令，由（1）,（2）两式得,令则.3 可交换矩阵的应用3.1 利用矩阵可交换性,求矩阵的方幂例1 计算, 是正整数.解 设, 由于,因为与可交换，所以由二项式定理得 ,即.例2 计算 , 是正整数.解 设, 因为,又因为与可交换，所以由二项式定理得 即.例3 计算 是正整数.解 设, 因为,所以当时，又和是可交换的，所以由二项式定理得， 即.例4 设 对任意正整数，求.解 令 则，又，设故利用矩阵乘法的结合律得其中从而，因此 注意到：移项，得从而有，所以即的主对角线上的元均为而其余元素均为.从以上各例的求解过程中，我们可以看到此种类型的题的解法都是把复杂的矩阵变成两个可交换矩阵的和，再利用二项式定理，求出最后结果。而在将一个矩阵分解成两个矩阵的和时，这两个矩阵最好简单点，它们中至少有一个矩阵的某次幂为零矩阵，这样再运用二项式定理算矩阵次幂就非常简单了。3.2 利用矩阵可交换性,证明某些问题例5 （2002年浙江大学硕士生入学考试试题）设是阶复矩阵，其中是幂零矩阵而且，求证：.证明 由于，由性质2，存在阶可逆矩阵，使得同为上三角矩阵，又是幂零矩阵，故其特征值全为零. 于是，有，从而.故.例6 （2001年浙江大学硕士生入学考试试题）设是数域上阶矩阵且，求证：秩 秩秩秩.证明 设秩，秩. 由于，由性质2，存在阶可逆矩阵，使得 与同为上三角矩阵，即不妨设则 从而，秩秩秩秩.参考文献 1 北京大学数学力学系几何与代数教研室代数小组. 高等代数M . 北京:人民教育出版社,1978. 2 北京大学数学系. 高等代数(第三版) M. 高等教育出版社,2003. 3 韩锦扬. 矩阵乘法AB = BA 成立的两个充要条件与一个充分条件J . 工科数学,1995 ,11:169-170. 4 曾梅兰. 线性变换及矩阵可交换的性质与应用J. 孝感学院学报,2006,26:44-46. 306关于等幂和的一个新性质数计学院 李彬瑜摘要：等幂和是一个历史悠久的古老难题 ，曾有许多人进行了研究，它们在数论中有着重要的作用，本文运用同余原理和数论的方法来探讨等幕和的一个新的性质。证明了p为奇素数，m为奇数时，获得了的值;当p为奇素数,与m奇偶相异时，获得了，并证明了的解为无限集。关键词：等幂和 同余 数学竞赛 整除And so on and the power of a new nature Li Bin-yu(Guangxi University for Nationalities Institute of Mathematics and Computer Science of the 04 (2) classes Nanning, Guangxi 530006)Instructor: Wang Yunkui Abstract: such as power and is a long history of the ancient problems, there have been many people were studied, in a few of them plays a significant role in this, with more than principle, the use of several methods, such as screen and to explore a new nature . P surprising that the number of m is odd, given the value of the definition of ，when p is the odd prime, and m parity differences, as well as the definition of the given proof of the is the model for the solution of unlimited Set.Key words: Idempotent sum, Congruence,Mathematics Olympiad, divisibility1.等幂和与数学竞赛问题等幂和 （1）是一个历史悠久的古老难题。自从2000年前的希腊数学家阿基米德开，就吸引了国内外数学家的研究兴趣。1984年以后，陈景润与黎鉴，王云等人对此作了大量的贡献。至今仍有不少数学家在研究，很多方法不断涌现。究其原因，不仅是因为等幂和作为级数求和的典范，更重要的是，它的数论性质对波文猜想、居家猜想与素数判别等问题有着非常重要的作用，而且在研究方法上有很强的灵活性，又可为开拓创新思维的宝地，在各国数学竟赛中也常常有与此有关的题目.1993年中国数学奥林匹克国家队选拔考试的第一题是：对素数p 3，定义 （2） 求的值。 其实解决这个问题的实质是利用等幂和的整除性，求出对模的剩余，然后再带入题目中给定义的式子即可。本文除了解决了数学竞赛这一问题外，还由此进一步将推广到及 的研究。2.引理引理 设m为奇数，则有： （4）证明； 一方面，由首尾配对有 （5） 由于m为奇数，故有，故由（5）式有 另一方面，再由首尾配对有： （6） 同理 又由 于，故 引理 若p为素数，m、n，pn，则 （7）证明：设， 当时，由费尔马小定理有：当时而，故所以同理有 而当时， ，则有 当时，设为模的一个原根，则 故 同理，结合有引理 若m为奇数，则有 （8） （9） 证明： 由等幂和的定义有 故有这就获得了（8）式，再在（8）式模即得（9）式。引理4 若m为偶数，则有 （10）证明：由上式即得：引理5 当m、n均为自然数时，则有： （11）证明：当n时， 当n时，3.定理定理1 设p为奇素数，m 为奇数，则有 。 证明：因为m为奇数，则根据引理1有 故定理2 设p为奇素数，m为偶数，则有 （12） （13）证明： 由引理2有 （14） （15） 定理3 设p为奇素数，m为奇数，若 则有： （16）证明：当m=1时， 则 当时由引理2 有 又由引理3中式 有 故 综合、可得： 定理 4 设p3素数，定义 （17） 证明： S为无限集。 证明：令 由费尔马小定理有 而故即得S为无限集。4.数学竞赛问题的解决 由题可设对每一个素数p，存在一个原根g，使得构成模p的一个完全剩余系。根据定理1有： 若，则 ；若，即，则故5.结语 到目前为止很多人都对等幂和的性质我有关算计进行了大量的研究，并取得了丰硕的成果。本文虽然获得了一些结果，但是仍有许多问题没有改进和开发，尚待继续研究。如当m为偶数时，定理3有何类似结果？定理5中如果是变为时能否求出m的的全部解等等。因此我还将继续努力，寻找解决的方法。参考文献：1陈景润,黎鉴愚关于幂和问题的进一步研究.J科学通报，1985,30(17):1381 -13842陈景润，黎鉴愚关于等幂和问题.J科学通报，1985,30(4):316317.3 陈景润，黎鉴愚关于幂和公式的一般性质.J数学研究与评论，1986,(1):43-50.4王云葵，等幕和与bernoulli数的通解公式.J.广西大学学报，1999,24(4):31 8-3205 王云葵.伯努利数与波文猜想.广西民族学院学报(自然科学版). 1999. 5. (3)6 王云葵.等幂和研究及其新进展.玉林师专学报，1994,15(3):4-107 王云葵.等暴和与居加猜想.数学通讯.1992,(11):43-448 王云葵. 等幂和的分解及同余式链. 天中学刊.1999 .14(5):9 王云葵. 等幂和与判别素数的充要条件.数学通报.1996,(6):46-4710 王云葵. 等幂和与波文猜想.广西教育学院学报.1998.(1):104-111一种新的扫描线种子填充算法数计学院 黄小果摘 要：为了解决经典扫描线种子填充算法存在的重复扫描、栈操作频繁等问题，本文提出一种新的扫描线种子填充算法。新算法取扫描线上每个填充区域的中点作为种子入栈，在不增加栈数据结构的前提下，通过一定的策略，使得每个出栈的种子能最大限度地往上和往下进行单向填充。新的算法设计巧妙，充分利用了区域连通的性质和图形像素分布的特点，极大地减少重复扫描的次数和入栈的种子数量，从而节约了资源并使得填充速度得到了很大的提高。关键词：区域填充，连通区域，种子，种子填充算法A New Scan Line Seed Filling AlgorithmHuang XiaoguoGuangxi University for Nationalities College of Mathematics and Computer Science Nanning 530006Email:huangxgiq120Abstract: In order to solve the problem of the classic line scanning seed filling algorithm, such as repeat scan, stack operation frequently, this paper presents a new algorithm. New algorithm pushes the midpoint of the region as a seed into stack, at no additional stack data structure, under the premise through a strategy to make each stack of seed to maximize the bottom-up and down to One-way filled. The design of the new algorithm is very clever, and makes full use of regional connectivity to the nature and characteristics of the distribution of pixel graphics, greatly reducing the number of repeat scan and the number of seeds in the stcak, thus saving resources and making filling speed has been greatly improved.Keywords：regional filling，regional connectivity，Seed，Seed filling algorithm0 引言在图形学的应用中，常常要在指定的区域内填充上填充颜色或图案，即区域填充。如何高效地进行填充是填充算法要解决的重要问题。种子填充算法是区域填充的一种重要方法，在实际中得到了广泛地运用。种子填充算法的基本思想是从一个封闭区域内部的一个已知像素出发，通过某种方法找到区域内的所有像素，从而进行填充。常用的种子填充算法有：简单种子填充算法和扫描线种子填充算法。简单种子填充算法可以采用递归算法【2】，这种算法的原理和程序都很简单，但由于多次递归和占用大量资源，填充质量非常差。为此，可以采用栈结构来实现简单的种子填充算法【1】。其基本原理是：种子像素入栈；当栈非空时重复执行如下三步骤操作：（1）栈顶像素出栈；（2）将出栈像素置成多边形色；（3）按左、上、右、下顺序检查与出栈像素相邻的四个像素，若其中某个像素不在边界且未置成多边形色，则把该像素入栈。9653S1111114728图1 S出栈后，像素4、7、9等出现了重复入栈。如图1所示，S出栈后，其间出现了重复入栈的冗余。并且，这种算法仍然需要很大的存储空间以实现栈结构，所花费的时间也较多。经典扫描线种子填充算法也是为解决上述问题而提出的一种重要方法。此外，一些专家提出了基于链队的种子填充算法【3】，有效地解决了重复入栈的问题，在此不再赘述。这里需要指出的一个概念是区域的连通性。区域的连通性是指从区域上的一点出发，通过几个方向移动的组合，在不超出区域的前提下，达到区域的任意像素。如图2和图3所示，区域可以分为四向连通区域和八向连通区域两种。本文的讨论基于四连通区域，即从区域上的一点出发，通过上、下、左、右移动的组合，达到区域的任何像素。 图2 四向连通 图3 八向连通1 经典算法的描述与分析1.1经典算法描述假定填充区域边界像素颜色为boundary_color，区域要填充的颜色为fill_color。经典扫描线种子填充算法的原理是将种子像素入栈，当栈非空时做以下4步操作。步骤1：栈顶像素出栈。步骤2：对包含出栈像素的整个区间进行填充。步骤3：上述区间的最左、右记为xl和xr。步骤4：在区间检查与当前扫描线相邻的上下两条扫描线的有关像素是否全为边界像素或已填充的像素，若存在非边界，未填充的像素，则把每一区间的最右或最左像素取为种子像素入栈。1.2经典算法分析经典算法采取的方法是在任意一条扫描线与多边形的相交区间（含若干连续像素）中，只取一个像素作为种子入栈。显然，经典算法减少了入栈的种子数量，节省了存储空间。但是对经典算法更进一步地分析，我们可以发现经典算法存在以下不足：1、重复扫描。为了对当前线段填色和将上、下线段的种子入栈，需要对当前线段，上下扫描线进行扫描。在这个过程中会使得某些线段被重复扫描3次，这降低了程序的效率和运行速度。2、出现漏填。由于未遵循经典算法，出现了漏填现象。文献4认为经典算法会出现漏填，这是错误的。3、栈操作频繁。在对与当前扫描线相邻的上、下扫描线进行种子搜索时，每搜到一个填充区域，就要将种子入栈；同时每次开始对另一行搜索时都要先出栈。这样则占用了大量的存储空间，降低了效率。对于问题1和2的改进，专家们提出了许多行之有效的方法。例如文献5定义了如下新的结构体：typedef struct node int dx,dy,left,right,oldleft,oldright,flag; struct node *next;其中，dx，dy是种子坐标；flag为方向标志，取值+1和-1。作者根据flag的值进行单向填充，避免了重复扫描。显然，文献5在种子栈中加入了一些变量，使栈结构变得复杂。此外，栈操作频繁的问题还没有解决。2 新扫描线种子填充算法的描述与分析2.1算法的描述假定给定区域边界像素颜色为boundary_color，区域要填充的颜色为fill_color。将种子像素（x,y）入栈，当栈非空时执行以下操作：步骤1：栈顶像素出栈。步骤2：对包含栈顶像素的整个区间进行填充，并记下区间的最左、右值xl_old和xr_old，xl=xl_old，xr=xr_old；步骤3：向上填充。判断栈顶像素的上一个像素是否为边界且未填充。若不为边界且尚未填充，填充包含（x,y+1）的整个区间，并并更新xl和xr作为区间的最左、右值。判断是否有回溯，若有则回溯，确定种子并将其入栈。将（x,y+1）看成栈顶像素，继续执行步骤3；否则，寻找下一个种子入栈，之后转入步骤4。步骤4：向下填充。判断栈顶像素的下一个像素是否为边界且未填充。若不为边界且尚未填充，填充包含（x,y-1）的整个区间，并更新xl和xr作为区间的最左、右值。判断是否有回溯，若有则回溯，确定种子并将其入栈。将（x,y-1）看成栈顶像素，继续执行步骤4；否则，寻找下一个种子入栈，之后转入步骤5。步骤5：结束判断。如果种子栈为空，则算法结束；否则，转入步骤1。2.2算法的图示： 图4 图5 填充图示 种子栈图示 2.3算法的分析：2.3.1种子栈的数据结构：class QNode public:QNode();virtual QNode();public:POINT data;QNode *Next;其中，data记录种子的坐标，next为下一个种子。比起文献5，新算法种子栈的数据结构无须增加变量，更加简单明了。2.3.2算法的一些细节与处理：（1）关于算法步骤3和4中如何确定下一个种子：在这里笔者采用的方法是：将填充区域的中点入栈。代码如下：if(xl=xr) & p_viewClientDC-GetPixel(xl,y)!=fill_color &p_viewClientDC-GetPixel(xl,y)!=boundary_color)p.x=int(x+xl)/2);/p.x=xl;p.y=y;stackpush(p);elsep.x=int(x+xl-1)/2);/p.x=xl-1;p.y=y;stackpush(p);其中“p.x=int(x+xl-1)/2);”代码段就是确定区域中点。这样将能使每个种子能最大限度的往上或者往下填充，大大的减少了入栈的种子数量和节省了大量的时间。（2）回溯问题。 图6 向上填充时可能出现回溯的情况向上填充：如图6所示，同一条扫描线上出现多个填充区域时，可能需要回溯，否则会出现漏填。假设xl_old,xr_old为上条扫描线填充区域，xl,xr为当前扫描线的填充区域。当xlxr_old+2，xr+2xl_old时，则会出现回溯。此时，我们采取的办法是：取xl,xl_old-2，xr_old+2,xr，xr+2,xr_old，xl_old,xl-2的中点作为种子入栈。向上填充时，回溯问题的c+语言如下：if(xlxl_old)seek_seed(xl_old,xl-2,y0,fill_color,boundary_color);if(xrxr_old+1)seek_seed(xr_old+2,xr,y0-1,fill_color,boundary_color);if(xr+1xr_old)seek_seed(xr+2,xr_old,y0,fill_color,boundary_color);同样，向下填充时，以下情况会出现回溯：图7 向下填充时可能出现回溯的情况此时，我们取xl,xl_old-2，xl_old,xl-2，xr_old+2,xr，xr+2,xr_old的中点入栈。解决回溯的C+语言如下：if(xlxl_old)seek_seed(xl_old,xl-2,y0,fill_color,boundary_color);if(xrxr_old+1)seek_seed(xr_old+2,xr,y0+1,fill_color,boundary_color);if(xr+1xr_old)seek_seed(xr+2,xr_old,y0,fill_color,boundary_color);2.3.3新算法的特点：取扫描线上每个填充区域的中点作为种子入栈，每个出栈的种子都尽可能地往上或往下单向填充；从微观处了解像素点的分布情况，有效地解决了回溯的问题。2.3.4新算法的优点：新的算法大大地减少了种子入栈的数量和重复扫描的次数，从而节省了资源，提高了效率。2.3.5新算法的不足：新的算法虽然大大地减少了重复扫描的次数，但还不能完全消除重复扫描。除第一个种子外，其余出栈的种子往上或往下扫描时，会出现一次的重复扫描。如图4中的S2，当它出栈时还要扫描上面一条扫描线，但上面一条扫描线已经扫描过了，所以出现了重复扫描。3 新算法与经典算法的一些数据比较：笔者在Visual C+平台上对新的算法与经典算法进行比较。如图8所示，填充带圆形孔(R=100像素)的矩形填充区域（边长a=600像素）；如图9所示，填充带有任意孔的连通区域。试验结果表明新的算法不会出现漏填、错填等现象。 图8 带圆孔的矩形填充区域 图9 带孔的任意连通区域带圆孔的矩形填充区域（图8）带任意孔的连通区域（图9）填充像素填充时间入栈像素填充像素填充时间入栈像素经典算法【1,2】32633617s799486283s909新算法3263364s34486281s不大于404 结束语表面上看，新算法似乎比经典算法复杂。其实不然，只是新的算法设计更巧妙罢了。新算法在没有增加栈的数据结构的情况下，使得每个出栈的种子都尽可能地往上或往下单向填充，省去了经典算法寻找种子，进而进栈、出栈等繁杂的操作过程，减少了重复扫描和入栈的种子数量，从而节省了大量的运算时间和大量的存储空间。虽然新的算法没有完全的消除重复扫描，但比起经典算法，重复扫描的次数已经大大减少，几乎可以忽略不计。大量实验证明，新算法在填充时间、入栈像素等方面有了巨大的进步，比起经典算法具有更大的优越性。参考文献：1孙家广 等,计算机图形学(第三版)M.北京：清华大学出版社,1999.2张曦煌，杜俊俐.计算机图形学M.北京：北京邮电大学出版社,2007.3陈元琰，陈洪波.一种基于链队的种子填充法J,广西师范大学学报(自然科学版),2003,9：3033. 4李桂清，李陶深.扫描线种子填充算法的问题及改进J,广西大学学报(自然科学版),1998,9：207211.5孙燮华.扫描线种子填充算法的改进J.计算机工程,2000,12：142143.基于蚁群算法的多目标运输问题优化算法的研究数计学院 黄富平摘要 蚁群算法是一种崭新的仿生模拟进化算法，该算法在许多领域已经得到应用。多目标运输问题是一类很重要的优化问题，优化与求解较难。对此，提出了一种改进蚁群算法用于求解多目标运输问题，得到一组变量的权重后，用一定数量的蚂蚁在解空间中首先随机搜索，然后模拟蚂蚁寻食的方式，通过信息素来指引搜索。关键词：多目标优化；运输问题；蚁群算法Research of Multi-Objective Transportation Problem OptimizationAlgorithm Based on Ant Colony AlgorithmAbstract Ant Colony Algorithm is a brand-new bionic simulated evolutionary algorithm, whichhas been applied to many fields. Multi-objective transportation problems are very important optimization problems. Its hard to optimized or solved. An improved Ant Colony Algorithm to solve Multi-objective transportation problems is introduced. After setting up a set of weight for the parameters, the algorithmuses uses some ants search in the solution space first in a stochastic way then stimulate the food searching behavior of real ants to guide the search by the pheromone. Keywords：Multiobjective optimization；Transportation problem；Ant colony algorithm1.引言 随着运输网络的发展和货运量的增加，运输调度问题变得越来越复杂。以总运费最小为优化目标的单目标优化模型得到的解，往往并不是决策者最满意的解，人们希望得到的是多目标的最优解。目前，涌现出许多求解多目标优化问题的算法，如交互式多目标优化、模糊规划法 、遗传算法、表上作业法等，但遗传算法是目前人们用来求解该类问题的主要方法。蚁群算法作为一种新的仿生类进化算法是由Dorigo首先提出的, 该算法模仿蚂蚁觅食时的行为, 按照启发式思想, 通过信息传媒 费洛(Pheromone) 的诱导作用, 逐步收敛到问题的全局最优解。蚁群算法自问世以来表现出了强大的生命力, 较之以往的启发式算法不论在搜索效率上, 还是在算法的时间复杂度方面都取得了令人满意的效果。 该算法已被其他领域的专家所接受, 并运用到诸如工件排序、图着色、车辆调度、大规模集成电路设计、通信网络中的负载平衡问题等许多方面。本文尝试将蚁群算法用于多目标运输问题, 因为蚁群算法具有卓越的随机搜索寻优能力,而多目标运输问题非常适合蚁群算法的适用领域。这两方面结合必将在多目标运输问题的研究中取得较满意的结果。2. 蚁群系统模型介绍 据昆虫学家的观察和研究发现，生物世界中的蚂蚁有能力在没有任何可见提示下找出从其窝巢至食物源的最短路径，并能随环境的变化而变化适应性地搜索新的路径，作出新的选择。作为昆虫的蚂蚁在寻找食物源时，能在其走过的路径上释放一种蚂蚁特有的分泌物-信息素，使得一定范围内的其它蚂蚁能够察觉到并由此影响它们以后的行为。当一些路径上通过的蚂蚁越来越多时,其留下的信息素轨迹也越来越多，以致信息素强度增大(当然随时间的推移会逐渐减弱) ，后来蚂蚁选择该路径的概率也就越高，从而增加该路径的自催化行为。由于其原理是一种正反馈机制,因此，可将蚁群理解成所谓的增强型学习系统.蚁群算法就是源于这种智能协作行为的算法。作为一种通用型随机优化方法，它吸收蚁群中蚂蚁的行为特性,通过其内在搜索机制，在一系列困难的组合优化问题求解中取得成效。由于在模拟仿真中使用的是人工蚂蚁概念，因此有时亦称为蚁群系统。 以求解n个城市TSP的问题为例来说明蚁群系统模型。为了模拟实际蚂蚁的行为，m表示蚁群中蚂蚁的数量，表示城市i和城市j之间距离，表示t时刻位于城市i的蚂蚁个数，。表示t时刻在ij连线上残留的信息量。在初始时刻,设(c是常数),各条路径上的信息量相等。蚂蚁k()在运动过程中,根据各条路径上的信息量决定移动方向。表示在t时刻蚂蚁由位置i转移到位置j的概率:其中,表示蚂蚁k下一步允许选择的城市；、分别表示蚂蚁在运动过程中所积累的信息及启发式因子在蚂蚁路径选择中所起的不同作用。与真实蚁群系统不同,人工蚂蚁系统具有一定的记忆功能。这里用来记录蚂蚁k目前已经走过的城市。随着时间的推移,以前留下的信息逐渐消逝。用参数表示信息消逝的程度,经过n个时刻,蚂蚁完成一次循环。各路径上的信息量根据下式作调整:表示第k只蚂蚁在本次循环中留在路径ij上的信息量,表示本次循环中留在路径ij上的信息量:式中,Q是常数；是第k只蚂蚁在本次循环中所走过路径的长度。在初始时刻,其中, 。表示由城市i转移到城市j的期望 程度,可以根据某种启发算法具体确定。根据具体算法的不同,及的表达形式可以不同,要根据具体情况确定。3.多目标运输模型的蚁群算法 3.1多目标运输问题其数学模型如下 ：(1)其中：表示第i个产地的产量；表示第j个销地的销量；表示第q个目标函数的费用系数；为产地i销往销地j的销量；第一个约束保证由一个产地运出量不能超出该产地的产量；第二个约束为一个销地的需求必须满足；在上述模型中，称为产销平衡运输问题。 3.2多目标运输问题转化为单目标运输问题本文把多目标问题转化为单目标问题来求解,所用的方法是加权法。假设多目标的各个函数所对应的权重为,，各个目标函数的权重根据问题的需要而定。加权之后的综合目标为 (2)。3.3用外惩罚函数法把单目标约束问题转化为无约束问题 根据上述我们把(1)、（2）两式用外惩罚函数法转化成如下: Min 3.4蚁群算法求解单目标运输问题的基本思路蚁群算法是用大量的蚂蚁在搜索空间中做局部并行搜索，反复地对路径上的信息素的高浓度的偏好选择，用信息素来指导搜索，并引入了信息素的挥发机制来防止陷入局部解，加强之后得到全局最优解，基于蚁群算法，提出用于多目标运输的改进蚁群算法，用于加权后的总目标优化求解： (1)第一步为确定各个子目标函数权重,并建立搜索空间。预处理后得到各个子目标函数的权重向量 。然后通过对各个约束条件求解，得到搜索空间，一般为一个维空间中的凸子空间，记为 ，其中 ，的各个分量满足，在此空间中的每一个点对应一个满足约束条件的可行解。然后进行离散化处理，将各个分量的搜索范围等分成离散的点，再进行切分。在这里，我们对各个分量采用一样的划分粒度便于处理。要特别指出的是，在确定各个子目标函数的权重时，使用现成的手段进行预处理。经过改进的蚁群算法主要是处理权重确定后的总目标函数的最优化求解。(2) 第二步为使用Ant在搜索空间中进行搜索。将每个分量的取值区间等分成N 个点，那么就有N 种选择， 维决策量X 有种选择组合。将每个分量的N 个取值点看作N 个城市City。先将m 个蚂蚁Ant随机地放到 的N中的m个City上。搜索开始后，首先进行随机搜索，使整个搜索空间得到初步的信息素分布，为下一阶段的概率搜索打好铺垫，Ant按照转移概率从的一个City(i, j,h)移动到的一个City(i,j+1,k)上，显然 。称 中的N 个City组成一个层 ，一共有个层，层间的先后顺序是可以随机的，不影响最后优化的结果。每只Ant从开始，层层转移，一直到达 ， 走过的路径 对应一个解，计算出对应的多目标优化函数值。(3) 更新路径上的信息素，得到当前最优解。所有蚂蚁得出解后，更新City(i, j，h)与City(i,j+1,k)之间路径 上的信息素为：，其中 为挥发系数，可经过试验得出经验值，一般可取较小的正值， 为m 只蚂蚁在路径上留下的新增信息素的总量，每次路径走过之后都要按照更新算法更新路径上的信息素。由于信息素与目标优化值成反比，当所得出的解 所对应的多目标优化值越小，那么在上留下的信息素越大。这样就对搜索做出了指导，通过反复运算之后，最优解将逐渐加强，并且保持稳定，由于挥发机制的作用，弱势解将逐渐被弱化，最后导致其被淘汰。同时，考虑权重的学习与更新，则在一轮搜索后，调整权重来调整加权后的总目标函数，最优解的搜索可以根据优化目标的实际需要而通过权重的变化而得到指导。让m只Ant做多次搜索之后得出一个当时最优解，然后将的各个分量细化重新建立搜索空间，重复以上过程，依次得到当停机条件满足的时候得到最优解并输出。4.结束语 蚁群算法作为通用型随机优化方法是根据蚂蚁觅食时的行为特性而设计的, 该算法能在非常困难的情况下搜索到运输问题的最优解。蚁群算法至今仍处于萌芽时期, 不管是理论还是应用都尚未成熟,因此有关这方面的研究仍需继续下去, 而在多目标运输中的应用也只是其中一例。如果能在参数设计方面取得突破, 相信该算法必能为许多领域的难题提供强有力的解决手段和工具。本文讨论了改进的ACA算法思想以及在多目标运输问题的最优解求解中的应用，该算法通过随机搜索同概率搜索结合，多个Ant并行求解，具有快速并能得到多个全局最优解的优点，现阶段特别针对加权后的总目标优化求解。参考文献:(1) 高 尚 杨静宇 . 群智能算法及其应用 中国水利水电出版社。(2) 张 军 胡晓敏 罗旭耀 . 蚁群优化 清华大学出版社。(3) 段海滨 蚁群算法原理及其应用 科学出版社。(4) 李士勇 蚁群算法及其应用 哈尔滨工业大学出版社。(5) 卢开澄 单目标、多目标与整数规划 清华大学出版社。南宁信息产业发展存在的问题与对策研究数计学院 黄德智【摘 要】本文通过详实的相关调查和统计资料，对南宁的信息生产业、传输业、设备制造业、服务业等方面进行分析，得出现阶段南宁信息产业各方面发展的具体情况。由现状进一步研究南宁信息产业在区域经济发展中所面临的形势和存在的问题，着重从中国东盟自由贸易区、泛北部湾区域经济区、信息产品技术、信息产业基础设施和人才等七个方面阐述南宁信息产业发展存在的问题。针对形势和问题，从南宁信息产业发展方向、区域经济发展、产品特色等五个方面提出具有可行性的建议和对策。【关键词】信息产业；区域经济；面临形势；存在问题；发展对策 Nanning development of the information industry and the problems CountermeasuresHuang De Zhi (Dept. of Mathematics and Computer Science, Guangxi Universityfor Nationality Nanning 530006,China)【Abstract】Through detailed investigation and statistical information, this paper analyses the information production industry, transmission industry, equipment manufacturing, and service industry of Nanning, and then obtains the concrete situation of the development of the information industry development of Nanning in different aspects at present days. And then after the study in the situation and current problems that exist in the information industry in Nanning, this paper focuses on China- ASEAN Free Trade Area, pan-Beibu Gulf economic zone, and information technology products, information industry infrastructure and information professional, from which expanding on the existing problems that Nanning has in the development of information industry. In consideration for the situation and problems, from the five aspects such as the direction of the development of information industry in Nanning, the regional economic development, and product characteristics, this paper finally raises the feasibility of the recommendations and countermeasures.【Key words】the information i
展开阅读全文