基于进化算法的机器人联盟优化问题 开题报告.doc
约6页DOC格式手机打开展开
基于进化算法的机器人联盟优化问题 开题报告,一、本课题设计（研究）的目的：多机器人系统联盟是多机器人协作的重要方法，联盟的优化问题是解决如何有效，快速的把系统中各个机器人组织起来结成任务联盟，使系统能灵活、高效的完成某个任务，避免任务的死锁问题和资源的浪费问题，充分发挥系统的优势，降低任务成本，提高工作效率。[10] 现在，联盟形成己经成为多机器人系统研究的一个...
内容介绍
此文档由会员 wanli1988go 发布
一、 本课题设计（研究）的目的：
多机器人系统联盟是多机器人协作的重要方法，联盟的优化问题是解决如何有效，快速的把系统中各个机器人组织起来结成任务联盟，使系统能灵活、高效的完成某个任务，避免任务的死锁问题和资源的浪费问题，充分发挥系统的优势，降低任务成本，提高工作效率。[10]
现在，联盟形成己经成为多机器人系统研究的一个重要方面。基于生物学自然遗传进化的遗传算法，是目前一种较成熟的进化算法;是一种新的全局优化搜索算法;是解决复杂问题的有效方法。遗传算法具有很好的鲁棒性，这是其他普通的优化搜索算法所无法比拟的。它采用了许多独特的方法和技术，利用选择、交叉和变异等遗传算子构成的随机技术来指导对搜索空间进行高效搜索，被认为是目前最好的搜索算法之一。近些年来，随着计算机硬件技术的不断提高以及对遗传算法的研究的深入，遗传算法的并行实现研究取得了许多成果。鉴于多智能体系统 (特别是大规模智能体系统)中联盟形成的解空间的复杂性、多智能体系统的分布并行性以及遗传算法的特性，研究运用遗传算法来实现联盟形成和解决联盟优化问题具有重要的意义。
基本要求：
（1） 选择合适的编码方式如 0-1编码或实数编码；
（2） 使问题空间中的解能采用遗传算法中的染色体来描述；
（3） 对遗传算法中的相关部分 (如编码、交叉、变异等)进行设计，提出新的联盟优化算法；
（4） 针对某一具体联盟问题，并给出模拟实验结果，说明改进算法的优点与特点。
二、 设计（研究）现状和发展趋势：
研究现状：
1) 在联盟形成方面：
联盟是多Agent系统(MAS)的重要合作方法。Agent间通过组成联盟可以提高求解问题的能力，获得更多的利益。
目前在MAS中，联盟形成的基本理论是N 人合作对策论理论，如Shapley值、核、核心等．N 人合作对策主要考虑如何划分联盟值，检查划分的稳定性和公平性，使Agent在决策时愿意形成全局最优联盟；它没有考虑算法，只考虑解的存在性，也不考虑计算资源、通信开销和计算分布等要求．
随着MAS的发展，研究人员从计算可实现的角度研究联盟生成，并提出了一些相关算法Sandholm[11(4,5)]、 胡山立[11(6)]徐晋晖[11(7)]基于“联盟结构”求解多任务的Agent联盟，联盟的生成过程就是在联盟结构图中进行搜索．这些算法大多通过约束条件来裁剪搜索树，减少搜索空间，在降低了算法复杂度的同时也牺牲了对最优解的求解．Sen[11(8)] 、骆正虎[11(9)]基于遗传算法求解Agent联盟，在可接受的时间内求解的质量有所提高. 。陈振洲[13]等的工作主要讨论非高一附加的多智能体环境，为多个智能体提供一个明显的联盟形成机制,在他们的研究中，联盟值取决于联盟资源的耗费和完成任务所得的利益。
此外， Shehory和Kraus[13（2）]提出了一种合作的联盟结构产生算法——最大化整体的利益，即Agents都是非自私的。在这种Agents中，收益分配问题不需要讨论。该分布算法形成不相交的联盟，并将任务分配给联盟，且每个联盟每次只能执行一个任务。Klusch和Shehory[13(4, 8)]对功利的联盟形成进行了讨论，提出了一种面向核的稳定的联盟形成算法KCA (Kernel-OrientedCoalitionAlgorithm)。该算法能够在多项式时间内为信息Agents找出一个稳定的联盟。另外，韩莉等[11]利用基于并行蚁群算法实现了多机器人联盟的组成。
2) 在遗传算法方面：
自从1983年Goldberg在他的博士论文中第一次把遗传算法用于实际的工程系统——煤气管道的优化后，遗传算法在其他工程领域也得到了广泛的应用，如机器学习、模型识别、神经网络参数结构优化、飞船控制系统优化等。在遗传算法的理论研究方而，主要是防止早熟收敛，有众多的研究者对这个问题做了大量的工作。王煦法等，根据生物免疫原理，提出了基于免疫原理的遗传算法;赵明旺将最速下降法和遗传算子结合，得到了新的用于连续函数全局优化的混合数值算法;郑金华等提出了“狭义遗传算法”，创造性的抛开了变异算子，在解决单峰连续问题时表现出极好的效果；蒙祖强等提出的基于切平面土升的狭义遗传算法，可以很好地解决多元 (连续)函数的优化问题。此外，人们对遗传算法的并行实现也做了大量的研究。己经提出了四种基本的并行遗传算法模型: 1.全局并行遗传算法 (GPGA) ; 2.粗粒度并行遗传算法 ((CPGA); 3.细粒度并行遗传算法 FPGA; 4.混合并行遗传算法 (HPGA)。在这四种基本模型的基础上，不同领域的研究者根据具体问题的不同也提出了其他一些并行遗传算法模型。
发展趋势：
现在，联盟形成己经成为多机器人系统研究的一个重要方面。基于生物学自然遗传进化的遗传算法，是目前一种较成熟的进化算法;是一种新的全局优化搜索算法;是解决复杂问题的有效方法。遗传算法具有很好的鲁棒性，这是其他普通的优化搜索算法所无法比拟的。它采用了许多独特的方法和技术，利用选择、交叉和变异等遗传算子构成的随机技术来指导对搜索空间进行高效搜索，被认为是目前最好的搜索算法之一。近些年来，随着计算机硬件技术的不断提高以及对遗传算法的研究的深入，遗传算法的并行实现研究取得了许多成果。遗传算法在形成Agent联盟(尤其在大规模Agent系统)中具有广阔的应用前景。[12]
三、 设计（研究）的重点和难点，拟采用的途径（研究手段）
重点:
根据多智能体系统 (特别是大规模智能体系统)中联盟形成的解空间的复杂性、多智能体系统的分布并行性以及遗传算法的特性，主要任务如下：
1. 建立智能体联盟/联盟结构问题的数学模型并研究怎样运用遗传算法来实现联盟形成以及算法的并行实现问题。
2. 针对单个不可分割的任务，提出基于遗传算法的单个联盟形成算法。针对己经分割成几个子任务 (子任务之间没有优先关系)的任务，提出基于遗传算法的联盟结构形成算法。并对上述两种算法给出模拟实验结果。
难点：
与其他的最优化问题一样，联盟形成问题需要在复杂而庞大的搜索空间中寻找最优解或满意解，在求解此类问题时，如果遍历整个搜索空间，就会产生搜索的组合爆炸，在多项式时间内无法完成搜索。因此，在使用遗传算法解决联盟优化问题时，难点在于：
1. 如何利用遗传算法一方面使得寻找最优解或可行解的开销极大地减少，另一方面使它所找到..
多机器人系统联盟是多机器人协作的重要方法，联盟的优化问题是解决如何有效，快速的把系统中各个机器人组织起来结成任务联盟，使系统能灵活、高效的完成某个任务，避免任务的死锁问题和资源的浪费问题，充分发挥系统的优势，降低任务成本，提高工作效率。[10]
现在，联盟形成己经成为多机器人系统研究的一个重要方面。基于生物学自然遗传进化的遗传算法，是目前一种较成熟的进化算法;是一种新的全局优化搜索算法;是解决复杂问题的有效方法。遗传算法具有很好的鲁棒性，这是其他普通的优化搜索算法所无法比拟的。它采用了许多独特的方法和技术，利用选择、交叉和变异等遗传算子构成的随机技术来指导对搜索空间进行高效搜索，被认为是目前最好的搜索算法之一。近些年来，随着计算机硬件技术的不断提高以及对遗传算法的研究的深入，遗传算法的并行实现研究取得了许多成果。鉴于多智能体系统 (特别是大规模智能体系统)中联盟形成的解空间的复杂性、多智能体系统的分布并行性以及遗传算法的特性，研究运用遗传算法来实现联盟形成和解决联盟优化问题具有重要的意义。
基本要求：
（1） 选择合适的编码方式如 0-1编码或实数编码；
（2） 使问题空间中的解能采用遗传算法中的染色体来描述；
（3） 对遗传算法中的相关部分 (如编码、交叉、变异等)进行设计，提出新的联盟优化算法；
（4） 针对某一具体联盟问题，并给出模拟实验结果，说明改进算法的优点与特点。
二、 设计（研究）现状和发展趋势：
研究现状：
1) 在联盟形成方面：
联盟是多Agent系统(MAS)的重要合作方法。Agent间通过组成联盟可以提高求解问题的能力，获得更多的利益。
目前在MAS中，联盟形成的基本理论是N 人合作对策论理论，如Shapley值、核、核心等．N 人合作对策主要考虑如何划分联盟值，检查划分的稳定性和公平性，使Agent在决策时愿意形成全局最优联盟；它没有考虑算法，只考虑解的存在性，也不考虑计算资源、通信开销和计算分布等要求．
随着MAS的发展，研究人员从计算可实现的角度研究联盟生成，并提出了一些相关算法Sandholm[11(4,5)]、 胡山立[11(6)]徐晋晖[11(7)]基于“联盟结构”求解多任务的Agent联盟，联盟的生成过程就是在联盟结构图中进行搜索．这些算法大多通过约束条件来裁剪搜索树，减少搜索空间，在降低了算法复杂度的同时也牺牲了对最优解的求解．Sen[11(8)] 、骆正虎[11(9)]基于遗传算法求解Agent联盟，在可接受的时间内求解的质量有所提高. 。陈振洲[13]等的工作主要讨论非高一附加的多智能体环境，为多个智能体提供一个明显的联盟形成机制,在他们的研究中，联盟值取决于联盟资源的耗费和完成任务所得的利益。
此外， Shehory和Kraus[13（2）]提出了一种合作的联盟结构产生算法——最大化整体的利益，即Agents都是非自私的。在这种Agents中，收益分配问题不需要讨论。该分布算法形成不相交的联盟，并将任务分配给联盟，且每个联盟每次只能执行一个任务。Klusch和Shehory[13(4, 8)]对功利的联盟形成进行了讨论，提出了一种面向核的稳定的联盟形成算法KCA (Kernel-OrientedCoalitionAlgorithm)。该算法能够在多项式时间内为信息Agents找出一个稳定的联盟。另外，韩莉等[11]利用基于并行蚁群算法实现了多机器人联盟的组成。
2) 在遗传算法方面：
自从1983年Goldberg在他的博士论文中第一次把遗传算法用于实际的工程系统——煤气管道的优化后，遗传算法在其他工程领域也得到了广泛的应用，如机器学习、模型识别、神经网络参数结构优化、飞船控制系统优化等。在遗传算法的理论研究方而，主要是防止早熟收敛，有众多的研究者对这个问题做了大量的工作。王煦法等，根据生物免疫原理，提出了基于免疫原理的遗传算法;赵明旺将最速下降法和遗传算子结合，得到了新的用于连续函数全局优化的混合数值算法;郑金华等提出了“狭义遗传算法”，创造性的抛开了变异算子，在解决单峰连续问题时表现出极好的效果；蒙祖强等提出的基于切平面土升的狭义遗传算法，可以很好地解决多元 (连续)函数的优化问题。此外，人们对遗传算法的并行实现也做了大量的研究。己经提出了四种基本的并行遗传算法模型: 1.全局并行遗传算法 (GPGA) ; 2.粗粒度并行遗传算法 ((CPGA); 3.细粒度并行遗传算法 FPGA; 4.混合并行遗传算法 (HPGA)。在这四种基本模型的基础上，不同领域的研究者根据具体问题的不同也提出了其他一些并行遗传算法模型。
发展趋势：
现在，联盟形成己经成为多机器人系统研究的一个重要方面。基于生物学自然遗传进化的遗传算法，是目前一种较成熟的进化算法;是一种新的全局优化搜索算法;是解决复杂问题的有效方法。遗传算法具有很好的鲁棒性，这是其他普通的优化搜索算法所无法比拟的。它采用了许多独特的方法和技术，利用选择、交叉和变异等遗传算子构成的随机技术来指导对搜索空间进行高效搜索，被认为是目前最好的搜索算法之一。近些年来，随着计算机硬件技术的不断提高以及对遗传算法的研究的深入，遗传算法的并行实现研究取得了许多成果。遗传算法在形成Agent联盟(尤其在大规模Agent系统)中具有广阔的应用前景。[12]
三、 设计（研究）的重点和难点，拟采用的途径（研究手段）
重点:
根据多智能体系统 (特别是大规模智能体系统)中联盟形成的解空间的复杂性、多智能体系统的分布并行性以及遗传算法的特性，主要任务如下：
1. 建立智能体联盟/联盟结构问题的数学模型并研究怎样运用遗传算法来实现联盟形成以及算法的并行实现问题。
2. 针对单个不可分割的任务，提出基于遗传算法的单个联盟形成算法。针对己经分割成几个子任务 (子任务之间没有优先关系)的任务，提出基于遗传算法的联盟结构形成算法。并对上述两种算法给出模拟实验结果。
难点：
与其他的最优化问题一样，联盟形成问题需要在复杂而庞大的搜索空间中寻找最优解或满意解，在求解此类问题时，如果遍历整个搜索空间，就会产生搜索的组合爆炸，在多项式时间内无法完成搜索。因此，在使用遗传算法解决联盟优化问题时，难点在于：
1. 如何利用遗传算法一方面使得寻找最优解或可行解的开销极大地减少，另一方面使它所找到..
