Abstract: In virtual network mapping, most studies only consider one mapping object, which can not reflect the interests of many aspects. To solve this problem, a Virtual Network Embedding algorithm based on Multi-objective Particle Swarm Optimization (VNE-MOPSO) was proposed by combining multi-objective algorithm and Particle Swarm Optimization (PSO) algorithm. Firstly, the crossover operator was introduced into the basic PSO algorithm to expand the search space of population optimization. Secondly, the non-dominated sorting and crowding distance sorting were introduced into the multi-objective optimization algorithm, which can speed up the population convergence. Finally, by minimizing both the cost and the node load balance degree as the virtual network mapping objective function, a multi-objective PSO algorithm was proposed to solve the Virtual Network Mapping Problem (VNMP). The experimental results show that the proposed algorithm can solve the VNMP, which has advantages in network request acceptance rate, average cost, average node load balance degree, and infrastructure provider's profit.

Key words: virtual network mapping, multi-objective optimization algorithm, Particle Swarm Optimization (PSO) algorithm, non-dominated sorting, crowding distance sorting, crossover operator

摘要： 在虚拟网络映射中，多数研究只考虑一个映射目标，不能体现多方的利益。为此，将多目标算法和粒子群算法结合，提出了一种基于多目标粒子群优化（PSO）的虚拟网络映射算法（VNE-MOPSO）。首先，在基本的粒子群算法中引入交叉算子，扩大了种群优化的搜索空间；其次，在多目标优化算法中引入非支配排序、拥挤距离排序，从而加快种群的收敛；最后，以同时最小化成本和节点负载均衡度为虚拟网络映射目标函数，采用多目标粒子群优化算法求解虚拟网络映射问题（VNMP）。实验结果表明，采用该算法求解虚拟网络映射问题，在网络请求接受率、平均成本、平均节点负载均衡度、基础设施提供商的收益等方面具有优势。

关键词: 虚拟网络映射, 多目标优化算法, 粒子群优化算法, 非支配排序, 拥挤距离排序, 交叉算子