论文部分内容阅读
【摘要】 优化算法有多种多样,且都有一定得应用背景。本文提出基于社会网络的智能优化算法。社会网络映射出了全局感知、交叉和变异、种群划分等相融合的优化思想。该算法的提出解决了以往优化算法只满足单一背景与实际情况复杂多样的矛盾。更好的解决了关于优化的相关问题。
【关键词】 社会网络 优化 算法
一、引言
优化是一个古老的问题,追求最优目标一直是人类的理想,在人们长期的探讨和研究中,发展了许多确定有效的优化方法,如牛顿法、共轭梯度法等。当今的许多科学研究和工程实践领域,例如机械设计、航空航天、网络通信、作业调度、图像处理、生命科学等都存在如何从多个方案中科学合理地提取最佳方案的问题。随着社会的不断进步,优化问题变得越来越复杂,传统的优化算法在计算速度、精确度等方面都远不能满足要求。为了满足社会进步对优化算法的需求,国内外研究者受自然规律和生物群体智能行为的启发,开发了各种各样的优化算法。例如,模拟人脑神经元连接机制的神经网络,模拟自然进化机制的进化计算(如遗传算法、进化规划、进化策略等),模拟生物群体智能行为的群智能优化算法(如蚁群算法、微粒群算法等),模拟物理原理的优化算法(如模拟退火算法)。由于这些算法是受不同自然规律和生物群体智能行为的启发而提出的,因此在对各种优化问题的求解过程中,这些算法均表现出了各不相同的智能行为和优化优势。
二、国内外研究现状
近年来,为了提高优化算法的全局寻优能力,国内外研究者的一般做法是将不同优化算法的各自优点结合起来,形成了多学科相互交叉、渗透的优化算法。优化算法的交叉研究大体上可分为以下三类:(1)利用智能个体的全局感知来增强全局的收敛性能:研究者主要是将万有引力、库仑力与粒子群优化算法进行了结合,算法中个体的行为要受到其它个体万有引力、库仑力等合力的影响,即个体能够全局感知。算法的模型仍然沿用了粒子群数学模型的“位置+位移量”框架,这些算法包括中心力算法、类电磁机制算法、万有引力搜索算法、拟态物理算法[1]。这类算法模拟的是一个动态的物理运动过程。在这类算法中,学者们仅仅表明了个体具有全局感知的能力,但对个体以什么样的方式进行全局感知却没有进行深入的研究。(2)利用交叉、变异来提高种群的多样性:将万有引力与交叉、变异结合起来提出了最大引力优化算法,算法中的万有引力只是一个测度,算法中的交叉和变异是基于万有引力现象进行的,从而该算法与遗传算法有着本质性的区别。对粒子群优化算法获得的最优解进行了交叉和变异,与遗传算法盲目的交叉和变异相比,能够以更大的概率逼近全局最优解。(3)将种群划分为相对独立的种群子系统以提高算法的并行性、预防种群多样性的过快损失:作者主要将生物学中的小生境概念应用于遗传算法、粒子群算法和克隆算法中。另外,天体系统粒子群算法,该算法参照天体系统模型,将种群划分为多个相对独立的天体系统,每个系统按照自己的运行规则在不同的空间中运行。这些算法既提高了算法的并行性,又易于保持种群的多样性,避免早熟收敛现象的发生。
由以上对智能优化算法当前研究现状的分析发现,这些算法或者利用智能个体的全局感知来增强全局的收敛性能,或者利用交叉、变异来提高种群的多样性,或者将种群划分为相对独立的种群子系统来提高算法的并行性、预防种群多样性的过快损失。随着科技领域中优化问题的复杂化及其对优化算法要求的不断增加,研究从某些自然规律和生物群智能现象中得到启发以融合目前各类优化算法的优点,无疑具有十分重要的现实意义。
三、“社会网络”简介
“社会网络”是由Auguste Comte提出的一个学科词汇,是指社会个体成员之间因为互动而形成的相对稳定的关系体系。社会网络具有较强的生命力,能够有效地改善算法的性能。
社会网络的研究对象是人类自身行为和人类群体所表现出的团体行为。美国社会学家Mark Granovetter提出了关系强度的概念[2],指出(1)强关系维系着团体内部的关系,而弱关系在团体之间建立了纽带联系;(2)与强关系相比,弱关系更能跨越其社会界限去获得信息和其他资源。美国社会学家Ronald Burt则提出了结构洞理论,认为结构洞的中间人具有更多的机会获取“信息利益”和“控制利益”,从而比网络中其他位置上的成员更具有竞争优势[3]。
四、“社会网络”与优化算法之间的映射分析
与神经网络在解空间的梯度下降、粒子群在解空间的飞翔、遗传基因在解空间的交叉与变异、人工免疫抗体在解空间的复制、交叉和变异等优化本质[4]不同,基于社会网络的智能优化算法是以信息以及个体成员在社会网络中获取、累积、运用和传递信息为优化机理的,是信息流形成的一种社会网络个体成员之间的稳定的关系体系。本文提出的社会网络映射出了全局感知、交叉和变异、种群划分等相融合的优化思想。首先,社会网络中的团体不仅能够体现出优化算法的种群划分思想,而且团体之间的弱关系还能够使网络中个体成员获得全网感知的能力;其次,信息在社会网络中由个体成员和团体进行传播,因此,在传播过程中信息不免会掺杂个体成员和团体自身的因素(情感、经验、恶意),这将导致信息发生变化,体现了优化算法的交叉和变异思想;再次,社会网络中个体成员和团体获取、运用和传递信息的能力将最终在網络中形成相对稳定的关系体系。由于社会网络体现了优化算法全局感知、交叉和变异、种群划分的融合思想,因此由社会网络映射并体现这种融合思想的智能优化算法也必将具有全局收敛特性、并行性和种群多样性等特性,而且能够有效地避免算法陷入局部极小值。
五、基于社会网络的智能优化算法中社会内部个体成员信息的获取和积累研究
优化算法中个体对信息的获取和累积采用的规则是“子群内个体之间的吸引与排斥规则”。这里的“吸引与排斥”是指对社团内个体对对方传递的信息所持的学习态度,可理解为“采纳与排斥”。与基于拟态物理学优化算法的合力的不同,子群内个体之间的吸引与排斥是在局部空间内进行的,另外,个体之间的吸引与排斥的程度与个体的适应值相关。
具体规则可描述为:若个体j的适应值优于个体i的适应值,则个体i将采纳个体j的信息,表现为吸引规则,而个体j将排斥个体i的信息,表现为排斥规则。个体i采纳个体j的信息的程度,与个体j在社团内所有优于个体i的个体中的位次有关;而个体j将排斥个体i的信息的程度,与个体i在社团内所有劣于个体j的个体中的位次有关。
对个体成员信息的获取和累积建模,描述如下:
六、结束语
在社会网络优化算法中,还涉及到更多方面的深入研究和改进,比如包括:社团最好个体成员之间信息的获取和累积研究;社团结构洞的中间成员的信息获取和累积研究;个体成员对信息的运用研究;信息的交叉与变异研究;社会网络中社团的划分研究等。希望随着后期的深入研究,可以得到更加优良的优化算法。
【关键词】 社会网络 优化 算法
一、引言
优化是一个古老的问题,追求最优目标一直是人类的理想,在人们长期的探讨和研究中,发展了许多确定有效的优化方法,如牛顿法、共轭梯度法等。当今的许多科学研究和工程实践领域,例如机械设计、航空航天、网络通信、作业调度、图像处理、生命科学等都存在如何从多个方案中科学合理地提取最佳方案的问题。随着社会的不断进步,优化问题变得越来越复杂,传统的优化算法在计算速度、精确度等方面都远不能满足要求。为了满足社会进步对优化算法的需求,国内外研究者受自然规律和生物群体智能行为的启发,开发了各种各样的优化算法。例如,模拟人脑神经元连接机制的神经网络,模拟自然进化机制的进化计算(如遗传算法、进化规划、进化策略等),模拟生物群体智能行为的群智能优化算法(如蚁群算法、微粒群算法等),模拟物理原理的优化算法(如模拟退火算法)。由于这些算法是受不同自然规律和生物群体智能行为的启发而提出的,因此在对各种优化问题的求解过程中,这些算法均表现出了各不相同的智能行为和优化优势。
二、国内外研究现状
近年来,为了提高优化算法的全局寻优能力,国内外研究者的一般做法是将不同优化算法的各自优点结合起来,形成了多学科相互交叉、渗透的优化算法。优化算法的交叉研究大体上可分为以下三类:(1)利用智能个体的全局感知来增强全局的收敛性能:研究者主要是将万有引力、库仑力与粒子群优化算法进行了结合,算法中个体的行为要受到其它个体万有引力、库仑力等合力的影响,即个体能够全局感知。算法的模型仍然沿用了粒子群数学模型的“位置+位移量”框架,这些算法包括中心力算法、类电磁机制算法、万有引力搜索算法、拟态物理算法[1]。这类算法模拟的是一个动态的物理运动过程。在这类算法中,学者们仅仅表明了个体具有全局感知的能力,但对个体以什么样的方式进行全局感知却没有进行深入的研究。(2)利用交叉、变异来提高种群的多样性:将万有引力与交叉、变异结合起来提出了最大引力优化算法,算法中的万有引力只是一个测度,算法中的交叉和变异是基于万有引力现象进行的,从而该算法与遗传算法有着本质性的区别。对粒子群优化算法获得的最优解进行了交叉和变异,与遗传算法盲目的交叉和变异相比,能够以更大的概率逼近全局最优解。(3)将种群划分为相对独立的种群子系统以提高算法的并行性、预防种群多样性的过快损失:作者主要将生物学中的小生境概念应用于遗传算法、粒子群算法和克隆算法中。另外,天体系统粒子群算法,该算法参照天体系统模型,将种群划分为多个相对独立的天体系统,每个系统按照自己的运行规则在不同的空间中运行。这些算法既提高了算法的并行性,又易于保持种群的多样性,避免早熟收敛现象的发生。
由以上对智能优化算法当前研究现状的分析发现,这些算法或者利用智能个体的全局感知来增强全局的收敛性能,或者利用交叉、变异来提高种群的多样性,或者将种群划分为相对独立的种群子系统来提高算法的并行性、预防种群多样性的过快损失。随着科技领域中优化问题的复杂化及其对优化算法要求的不断增加,研究从某些自然规律和生物群智能现象中得到启发以融合目前各类优化算法的优点,无疑具有十分重要的现实意义。
三、“社会网络”简介
“社会网络”是由Auguste Comte提出的一个学科词汇,是指社会个体成员之间因为互动而形成的相对稳定的关系体系。社会网络具有较强的生命力,能够有效地改善算法的性能。
社会网络的研究对象是人类自身行为和人类群体所表现出的团体行为。美国社会学家Mark Granovetter提出了关系强度的概念[2],指出(1)强关系维系着团体内部的关系,而弱关系在团体之间建立了纽带联系;(2)与强关系相比,弱关系更能跨越其社会界限去获得信息和其他资源。美国社会学家Ronald Burt则提出了结构洞理论,认为结构洞的中间人具有更多的机会获取“信息利益”和“控制利益”,从而比网络中其他位置上的成员更具有竞争优势[3]。
四、“社会网络”与优化算法之间的映射分析
与神经网络在解空间的梯度下降、粒子群在解空间的飞翔、遗传基因在解空间的交叉与变异、人工免疫抗体在解空间的复制、交叉和变异等优化本质[4]不同,基于社会网络的智能优化算法是以信息以及个体成员在社会网络中获取、累积、运用和传递信息为优化机理的,是信息流形成的一种社会网络个体成员之间的稳定的关系体系。本文提出的社会网络映射出了全局感知、交叉和变异、种群划分等相融合的优化思想。首先,社会网络中的团体不仅能够体现出优化算法的种群划分思想,而且团体之间的弱关系还能够使网络中个体成员获得全网感知的能力;其次,信息在社会网络中由个体成员和团体进行传播,因此,在传播过程中信息不免会掺杂个体成员和团体自身的因素(情感、经验、恶意),这将导致信息发生变化,体现了优化算法的交叉和变异思想;再次,社会网络中个体成员和团体获取、运用和传递信息的能力将最终在網络中形成相对稳定的关系体系。由于社会网络体现了优化算法全局感知、交叉和变异、种群划分的融合思想,因此由社会网络映射并体现这种融合思想的智能优化算法也必将具有全局收敛特性、并行性和种群多样性等特性,而且能够有效地避免算法陷入局部极小值。
五、基于社会网络的智能优化算法中社会内部个体成员信息的获取和积累研究
优化算法中个体对信息的获取和累积采用的规则是“子群内个体之间的吸引与排斥规则”。这里的“吸引与排斥”是指对社团内个体对对方传递的信息所持的学习态度,可理解为“采纳与排斥”。与基于拟态物理学优化算法的合力的不同,子群内个体之间的吸引与排斥是在局部空间内进行的,另外,个体之间的吸引与排斥的程度与个体的适应值相关。
具体规则可描述为:若个体j的适应值优于个体i的适应值,则个体i将采纳个体j的信息,表现为吸引规则,而个体j将排斥个体i的信息,表现为排斥规则。个体i采纳个体j的信息的程度,与个体j在社团内所有优于个体i的个体中的位次有关;而个体j将排斥个体i的信息的程度,与个体i在社团内所有劣于个体j的个体中的位次有关。
对个体成员信息的获取和累积建模,描述如下:
六、结束语
在社会网络优化算法中,还涉及到更多方面的深入研究和改进,比如包括:社团最好个体成员之间信息的获取和累积研究;社团结构洞的中间成员的信息获取和累积研究;个体成员对信息的运用研究;信息的交叉与变异研究;社会网络中社团的划分研究等。希望随着后期的深入研究,可以得到更加优良的优化算法。