基于离散粒子群算法求解复杂联盟生成问题

针对联盟生成问题现有解决方案的不足,提出复杂联盟和虚拟Agent的概念,设计一种基于多粒子群协同优化的复杂联盟串行生成算法,实现一个Agent可以加入多个联盟和一个联盟可以承担多个任务,在一定程度上解决了Agent资源和能力的浪费问题.实验结果证明了算法的有效性.     

多任务并发边缘计算环境中最优联盟结构生成策略

针对求解最优联盟结构时搜索空间大、效用低等问题，提出了一种基于离散最近过去位置更新策略的多进制离散粒子群优化（MDPSO-DRPPUS）算法。首先，使用基于索引的编码方式编码联盟结构。其次，将多目标优化问题转化为联盟结构的特征值函数。最后，使用MDPSO-DRPPUS算法进行最优联盟结构的搜索。实验表明，与多进制离散粒子群优化（MDPSO）算法和遗传算法（GA）相比，所提算法运行时间大幅度降低，联盟结构的效益、均衡性和边缘节点的完成任务效率都有所提高。     

无线传感器网络中带复杂联盟的自适应任务分配算法

针对无线传感器网络任务调度的实时性及节点计算及能量受限的特点,根据任务截止期赋予任务优先级,优先考虑高优先级任务,设计了一个无线传感器网络中带复杂联盟的自适应任务分配算法。为尽最大努力确保任务在截止期前完成,对截止期较为紧迫的任务采用历史信息生成历史联盟,并执行快速子任务分配算法;而对截止期较为宽裕的任务,在满足任务截止期约束条件下,以节点能耗和网络能量分布平衡为优化目标,采用矩阵的二进制编码形式,设计了一种离散粒子群优化算法以并行生成联盟,并执行基于负载和能量平衡的子任务分配算法。仿真实验结果表明所构造的自适应算法是有效的,在局部求解与全局探索之间能够取得较好的平衡,并能够在较短的时间内取得满意解。     

一种基于蚁群算法的多任务联盟串行生成算法

联盟生成是多Agent系统的一个关键问题,主要研究如何在多Agent系统中动态生成面向任务的最优Agent联盟.引入蚁群算法解决多任务联盟问题.提出了一种基于蚁群算法的多任务联盟串行生成算法,对于任务序列可依次生成全局最优联盟,避免了联盟死锁和资源浪费,同时算法基于蚁群系统的学习能力可以有效减少联盟生成的搜索时间和计算量,可实现性好.     

求解排列问题的分布估计离散粒子群优化算法

目前粒子群优化算法和分布估计算法较少用于解决排列编码组合优化问题,本文提出了一种新的适用于求解排列问题的分布估计离散粒子群优化算法.提出的算法结合粒子群优化算法和分布估计算法的思想,突破了标准粒子群优化算法速度-位移更新模式.新算法中每个粒子的信息一部分来自该粒子当前解排列与全局最优排列的最长公共子串,另一部分来自描述所有个体最优值分布信息的概率模型.这样粒子的当前解、所有个体最优值和全局最优值都参与了新解的生成过程,提出的算法秉承了粒子群优化算法的思想,同时具有更全面的学习能力,提高了算法的寻优能力以及避免陷入局部最优的能力.在两个经典的排列问题上的实验结果表明提出的算法具有良好的性能.     

求解独立任务调度问题的改进粒子群算法

独立任务调度问题是分布式系统中的一个NP难题.提出了基于实数编码和基于机器编码的两种改进粒子群算法.前者利用协同子群进化的方式进行问题寻优,后者通过重新定义粒子的位置更新方法,使粒子群算法更好地应用于组合优化问题.仿真结果表明,与遗传算法和基本粒子群算法相比,改进算法具有更快的收敛特性和更好的求解质量.     

WSN中结合双层编码和JPSO的多约束Steiner树算法

聚合树是无线传感器网络(WSN)中的一种典型的数据聚合技术。针对多目标约束的Steiner树问题(MCSTP),提出一种基于双层编码机制(TE)和跳跃粒子群优化(JPSO)的启发式算法构建最优树结构。首先,选择总能耗、网络寿命、收敛时间和通信干扰作为优化约束目标。然后,根据提出的双层编码方案对生成树的解进行编码,同时利用跳跃粒子群优化算法寻找帕累托最优解。最后,利用提出的混合适应度函数找出近似最优树结构。实验结果表明,JPSO-TE方法可以产生近似最优的树结构,具有高效性和可行性。     

基才一种QPSO算法的阵列天线方向图综合

方向图综合技术是智能天线中的一项关键技术。由于采用普通粒子群算法存在着易于早熟和局部寻优能力不足等缺点．为此本文提出一种基于量子位概率幅编码QPSO算法的阵列天线方向图综合技术,即在方向图综合中,QPSO算法采用量子位对粒子当前位置进行编码,用量子旋转门实现对粒子最优位置的搜索,用量子非门实现粒子位置的变异以避免早熟。实际应用表明基于量子位概率福编码QPSO的方向图综合技术是切实可行的,在多零点和低旁瓣约束情况下均可以取得良好的优化效果,具有很好的推广能力。     

采用威胁启发粒子群算法的无人机航路规划

针对复杂地形和威胁环境下的无人机航路规划问题,对粒子群算法进行了改进,提出了融入威胁启发机制的改进粒子群算法.充分利用无人机在任务区域中已知的威胁信息,将其作为威胁启发项,构成粒子群速度更新公式的一部分,有效丰富粒子群算法的搜索行为,增强粒子在搜索过程中的针对性和指导性.使用最小威胁曲面方法,降低粒子编码的维数,并采用...     

MIMO雷达中正交离散频率编码波形的设计北大核心CSCD

发射信号正交性能的好坏直接决定了多输入多输出(Multiple Input and Multiple Output,MIMO)雷达系统的性能。正交离散频率编码波形是一种较理想的准正交波形。首先给出了正交离散频率编码波形的模糊函数,然后以互相关能量为代价函数,运用改进的离散粒子群优化算法对正交离散频率编码波形进行优化排序设计,生成可应用于宽带MIMO雷达中的具有较好模糊特性的准正交信号。仿真结果验证了新算法的有效性,且随着码长的增加和编码排序的优化新的正交离散频率编码波形的互相关性能将变得更好,其对多普勒的容忍性与码长成反比,但是由于固有的特性其自相关性能与码长几乎无关。     

信任和效用关系约束的联盟结构生成

联盟结构生成是分布式人工智能的重要研究内容,一般仅依据智能体效用生成任意数量的联盟,这导致最优联盟结构生成的计算复杂度NP难。实际上,信任是合作的基础,信任关系对最终效用有直接的影响,应该综合考虑信任和效用关系。针对以上问题,该文扩展效用约束为信任和效用约束,用信任和效用二元组表示,以此作为联盟结构生成的依据。借鉴图割的s-t-cut算法,研究了基于信任和效用关系的联盟结构生成,在保证智能体个体理性和联盟稳定(无块)的前提下,使用信任和效用关系对网络进行切割,从而形成联盟。由此,该文提出了两种多项式时间的精确算法:信任关系约束下的MT-s-t-cut算法和信任效用关系约束下的MTU-s-t-cut算法,这两种算法均能够在多项式时间内得到最优联盟结构。仿真实验验证了信任关系影响所形成的联盟结构,社会整体效用随智能体数量的增加而增加,并且算法的运行时间远小于动态规划法(DP)和ODP-IP算法。     

Algorithms for Transitive Dependence-Based Coalition Formation

Coalition formation methods allow autonomous agents to join together in order to act as a coherent group in which they increase their individual gains by collaborating with each other. Although there are some research efforts toward coalition formation in multiagent systems (MAS), such as game theory-based approaches, these methods cannot be easily applied in real-world scenarios. Based on a novel social reasoning theory, namely, transitive dependence theory, this work proposes two dynamic coalition formation algorithms for coalition formation: 1) without and-action dependence and 2) with and-action dependence, respectively. While most related work addresses the problem of searching for the optimal coalition structure (CS), the proposed algorithms aim to find out the optimal coalitions for specific goals. Theoretical analysis and experimental results suggest that 1) the algorithm for coalition formation without and-action dependence is of polynomial complexity and is efficient, and 2) when the incidence rate of and-action dependence is not high, the anytime algorithm for coalition formation with and-action dependence is also efficient although it has relatively high complexity (NP-complete).     

Task coalition formation and self‐adjustment in the wireless sensor networks

Coalition is an essential mechanism in the multi‐agent systems in the research of task‐oriented area. Self‐interested agents coordinate their behaviors in a coalition to pursue a common goal and obtain payoffs. We propose the clustering‐based coalition formation and self‐adjustment mechanisms for tasks in the wireless sensor network. Before coalition formation, the management center clusters attributes of sensors to reduce the scale of searching space during coalition formation. And then an improved MAX–MIN ant colony optimization algorithm is adopted to resolve the problem of coalition formation. If a coalition member fails to fulfill a task, it can sponsor a negotiation with some noncoalition nodes to execute coalition self‐repairing autonomously. The stimulus‐response mechanism of wasp colony is introduced to determine the probability of response to the task invitation to avoid consuming extra energy. Simulation results show that our model efficiently reduces energy consumption and network traffic, decreases the number of dead nodes, and prolongs the lifetime of the networks. Copyright © 2012 John Wiley & Sons, Ltd.     

Joint resource allocation and interference management in the D2D uplink underlaying cellular networks

This paper investigates the problem of joint interference management and resource allocation in device-to-device (D2D) uplink underlaying cellular networks. To improve the D2D system sum throughput, an overlapping coalition formation game (OCFG) is proposed to achieve resource allocation. In the game, a novel initialization in term of the priority sequence is proposed to rapidly form the initial coalitions. During the coalition formation, the merging and splitting sequences are adopted to guide the order that D2D users merge in or split from the coalition. Here the splitting sequences are formed according to cross-tier interference strength and the merging sequence is based on matching theory. Besides, a power control scheme is formulated to optimize the power allocation. The performance of the proposed algorithm is analyzed and verified through simulations.

     

引入熟人集的Agent协作联盟构成

Agent联盟构成问题是一个复杂的组合优化问题,属于NP完全问题,其求解是很困难的.本文提出了一种Agent联盟构成策略,该策略在系统运行的初始阶段,保证任务分配的最优解.而在随后的运行中基于熟人集形成Agent联盟.该策略保证在接近任务分配优化的情况下,有效减少系统中的可能联盟数以及联盟形成过程中的通信开销和计算量,避免联盟形成过程中的盲目性,从而节省协商时间提高协商效率.     

On the capacity game of private fingerprinting systems under collusion attacks

The problem of fingerprinting in the presence of collusive attacks is considered. It is modeled as a game between a fingerprinter and a decoder on the one hand, and a coalition of two or more attackers on the other. The fingerprinter distributes, to different users, different fingerprinted copies of a host data (covertext ) embedded with different fingerprints. The coalition members create a forgery of the data while aiming at erasing the fingerprints in order not to be detected. Their action is modeled by a multiple-access channel (MAC). The decoder, who has access to the original covertext data, observes the forgery and decodes one of the messages in order to identify one of the members of the coalition. Motivated by a worst case approach, we assume that the coalition of attackers is informed of the hiding strategy taken by the fingerprinter and the decoder, while they are uninformed of the attacking scheme. A single-letter expression for the capacity is derived under the assumption that the host data is drawn from a memoryless stationary source and some mild assumptions on the operation of the encoder. It is shown that for a coalition consisting of L相似文献   

基于Petri网局部性的极大冲突集枚举算法

冲突是Petri网研究的重要主题.目前Petri网冲突研究主要集中于冲突建模和冲突消解策略,而对冲突问题本身的计算复杂性却很少关注.提出Petri网的冲突集问题,并证明冲突集问题是NP（Non-deterministic Polynomial）完全的.提出极大冲突集动态枚举算法,该算法基于当前标识的所有极大冲突集,利用Petri网实施局部性,仅计算下一标识中受局部性影响的极大冲突集,从而避免重新枚举所有极大冲突集.该算法时间复杂度为O（m²n）,m是当前标识的极大冲突集数目,n是变迁数.最后证明自由选择网、非对称选择网的极大冲突集枚举算法复杂度可降至O（n²）.极大冲突集枚举算法研究将为Petri网冲突问题的算法求解提供理论参考.     

Coordinated coalition formation in throughput‐efficient cognitive radio networks

In this paper, we consider the problem of joint coalition formation (CF) and bandwidth allocation in cognitive radio networks. We assume that the secondary links will be partitioned into disjoint coalitions, by which the available spectrum will be reused. On the other hand, we assume that the members of each coalition will transmit over orthogonal sub‐bands with the available spectrum being optimally allocated among them. We formulate the problem as a coordinated CF game, where the optimization is held at a secondary coordinator that has all the required channel information. Given these assumptions, we derive a closed‐form expression of the optimal bandwidth allocation for any given network partition, and we propose an efficient algorithm to reach a Nash‐stable partition (coalition structure), with the objective of improving the network throughput. Furthermore, we provide a probabilistic analysis of the stability of a grand structure and a singleton structure, and we employ this to obtain a lower bound on the stability of a general coalition structure (other than grand and singleton). Performance analysis shows that the proposed CF algorithm with optimal bandwidth allocation provides a substantial gain in the network throughput over existing CF techniques as well as the simple cases of singleton and grand coalitions. Copyright © 2015 John Wiley & Sons, Ltd.     

A coalition formation game based relay selection scheme for cooperative cognitive radio networks

In a cognitive radio network, cooperative communications between a primary user (PU) and a second user (SU) may be able to significantly improve the spectrum utilization, and thus, the network performance. To be specific, the PU can select a number of SUs as its relays to cooperatively transmit its data. In turn, these relays can be granted access to the licensed channel of the PU to transmit their data. In this paper, an effective cooperation strategy for SUs is presented. We formulate the problem of cooperative relay selection as a coalition formation game, and develop a utility function based on the game. The utility function considers various factors such as transmission power and noise level. With the utility function, a distributed coalition formation algorithm is proposed, which can be used by SUs to decide whether to join or leave a coalition. Such a decision is based on whether it can increase the maximal coalition utility value. We rigorously prove that our proposed coalition formation algorithm can terminate and reach a stable state. Finally, this paper demonstrates that the proposed scheme is able to enhance the network throughput via a simulation study.