无线传感器网络基于改进遗传算法的节点调度

节点调度问题是经典的NP-hard组合优化问题之一。为解决该问题提出了诸如蚁群算法、粒子群算法和遗传算法等智能算法，以遗传算法(genetic algorithm，GA)更为有效，但经典的遗传算法在解决节点调度问题时，其算法自身存在寻优速度慢，容易陷入局部最优。提出一种改进的轮盘赌优化方法，该方法基于适应度比例的选择，即用全部个体的选择概率来计算累计概率，产生完整的子代个体并保留其基因，避免陷入局部最优，进而快速精确地求出节点调度问题的最优解，实验结果表明，经过改进的遗传算法求解的路径长度、收敛性和运行时间等指标均有明显改善。

Node scheduling problem based on improved genetic algorithm for wireless sensor networks

The node scheduling problem is one of the classic NP-hard combinatorial optimization problems. In order to solve this problem, intelligent algorithms such as ant colony algorithm, particle swarm algorithm and genetic algorithm are proposed, but the genetic algorithm (GA) is more effective. However, when the classical genetic algorithm is used to solve the problem of node scheduling, the algorithm itself has a slow optimization speed and is easy to fall into local optimum. This paper presents an improved method of roulette optimization, which is based on the choice of fitness ratio, that is to calculate the accumulative probability with the selection probability of all individuals, to produce complete offspring and retain their genes, to avoid falling into local optimum, and to find the optimal solution of node scheduling problem quickly and accurately. The experimental results show that the path length, convergence and running time of the improved genetic algorithm are improved significantly.