Billiards Optimization Algorithm:A New Game-Based Metaheuristic Approach

Metaheuristic algorithms are one of themost widely used stochastic approaches in solving optimization problems.In this paper,a new metaheuristic algorithm entitled Billiards Optimization Algorithm(BOA)is proposed and designed to be used in optimization applications.The fundamental inspiration in BOA design is the behavior of the players and the rules of the billiards game.Various steps of BOA are described and then its mathematical model is thoroughly explained.The efficiency of BOA in dealing with optimization problems is evaluated through optimizing twenty-three standard benchmark functions of different types including unimodal,high-dimensional multimodal,and fixed-dimensionalmultimodal functions.In order to analyze the quality of the results obtained by BOA,the performance of the proposed approach is compared with ten well-known algorithms.The simulation results show that BOA,with its high exploration and exploitation abilities,achieves an impressive performance in providing solutions to objective functions and is superior and far more competitive compared to the ten competitor algorithms.

Distributed Optimal Variational GNE Seeking in Merely Monotone Games

In this paper, the optimal variational generalized Nash equilibrium(v-GNE) seeking problem in merely monotone games with linearly coupled cost functions is investigated, in which the feasible strategy domain of each agent is coupled through an affine constraint. A distributed algorithm based on the hybrid steepest descent method is first proposed to seek the optimal v-GNE. Then, an accelerated algorithm with relaxation is proposed and analyzed, which has the potential to further improve the convergence speed to the optimal v-GNE. Some sufficient conditions in both algorithms are obtained to ensure the global convergence towards the optimal v-GNE. To illustrate the performance of the algorithms, numerical simulation is conducted based on a networked Nash-Cournot game with bounded market capacities.

GENETIC ALGORITHMS AND GAME THEORY FOR HIGH LIFT DESIGN PROBLEMS IN AERODYNAMICS

A multi-objective evolutionary optimization method (combining genetic algorithms(GAs)and game theory(GT))is presented for high lift multi-airfoil systems in aerospace engineering.Due to large dimension global op-timization problems and the increasing importance of low cost distributed parallel environments,it is a natural idea to replace a globar optimization by decentralized local sub-optimizations using GT which introduces the notion of games associated to an optimization problem.The GT/GAs combined optimization method is used for recon-struction and optimization problems by high lift multi-air-foil desing.Numerical results are favorably compared with single global GAs.The method shows teh promising robustness and efficient parallel properties of coupled GAs with different game scenarios for future advanced multi-disciplinary aerospace techmologies.

Research on Different Heuristics for Minimax Algorithm Insight from Connect-4 Game

Minimax algorithm and machine learning technologies have been studied for decades to reach an ideal optimization in game areas such as chess and backgammon. In these fields, several generations try to optimize the code for pruning and effectiveness of evaluation function. Thus, there are well-armed algorithms to deal with various sophisticated situations in gaming occasion. However, as a traditional zero-sum game, Connect-4 receives less attention compared with the other members of its zero-sum family using traditional minimax algorithm. In recent years, new generation of heuristics is created to address this problem based on research conclusions, expertise and gaming experiences. However, this paper mainly introduced a self-developed heuristics supported by well-demonstrated result from researches and our own experiences which fighting against the available version of Connect-4 system online. While most previous works focused on winning algorithms and knowledge based approaches, we complement these works with analysis of heuristics. We have conducted three experiments on the relationship among functionality, depth of searching and number of features and doing contrastive test with sample online. Different from the sample based on summarized experience and generalized features, our heuristics have a basic concentration on detailed connection between pieces on board. By analysing the winning percentages when our version fights against the online sample with different searching depths, we find that our heuristics with minimax algorithm is perfect on the early stages of the zero-sum game playing. Because some nodes in the game tree have no influence on the final decision of minimax algorithm, we use alpha-beta pruning to decrease the number of meaningless node which greatly increases the minimax efficiency. During the contrastive experiment with the online sample, this paper also verifies basic characters of the minimax algorithm including depths and quantity of features. According to the experiment, these two characters can both effect the decision for each step and none of them can be absolutely in charge. Besides, we also explore some potential future issues in Connect-4 game optimization such as precise adjustment on heuristic values and inefficiency pruning on the search tree.

Economic Dispatch of Electrical Power System Based on the Multi-objective Co-evolutionary Algorithm

It is important to distribute the load efficiently to minimize the cost of the economic dispatch of electrical power system. The uncertainty and volatility of wind energy make the economic dispatch much more complex when the general power systems are combined with wind farms. The short term wind power prediction method was discussed in this paper. The method was based on the empirical mode decomposition (EMD) and ensemble empirical mode decomposition (EEMD). Furthermore,the effect of wind farms on the traditional economic dispatch of electrical power system was analyzed. The mathematical model of the economic dispatch was established considering the environmental factors and extra spinning reserve cost. The multi-objective co-evolutionary algorithm was used to figure out the model. And the results were compared with the NSGA-Ⅱ(non-dominated sorting genetic algorithm-Ⅱ) to verify its feasibility.

NUMERICAL METHOD BASED ON HAMILTON SYSTEM AND SYMPLECTIC ALGORITHM TO DIFFERENTIAL GAMES

The resolution of differential games often concerns the difficult problem of two points border value （TPBV）, then ascribe linear quadratic differential game to Hamilton system. To Hamilton system, the algorithm of symplectic geometry has the merits of being able to copy the dynamic structure of Hamilton system and keep the measure of phase plane. From the viewpoint of Hamilton system, the symplectic characters of linear quadratic differential game were probed; as a try, Symplectic-Runge-Kutta algorithm was presented for the resolution of infinite horizon linear quadratic differential game. An example of numerical calculation was given, and the result can illuminate the feasibility of this method. At the same time, it embodies the fine conservation characteristics of symplectic algorithm to system energy.

Development of Algorithm of Traditional Kei-Yen Game

Manipuri traditional game Kei-Yen, which originates from the ancient Meitei mythological story, is a mind game between two players of different mindsets, one has the mindset of killing (Kei), whereas the other (Yen) has the mindset of protecting itself and block the moves of Kei. We propose and develop an algorithm of this game by incorporating various possible logical tactics and strategies for a possible computer software of this game. Since this game involves various logical mind games, playing this game can improve our way of thinking, strategies, tricks and other skills related to mind game. In this play there is not the case of draw which means one has to win over the other at the end of the game. This game could become one of most interesting indoor national or international game.

Optimizing Polynomial-Time Solutions to a Network Weighted Vertex Cover Game

Weighted vertex cover(WVC)is one of the most important combinatorial optimization problems.In this paper,we provide a new game optimization to achieve efficiency and time of solutions for the WVC problem of weighted networks.We first model the WVC problem as a general game on weighted networks.Under the framework of a game,we newly define several cover states to describe the WVC problem.Moreover,we reveal the relationship among these cover states of the weighted network and the strict Nash equilibriums(SNEs)of the game.Then,we propose a game-based asynchronous algorithm(GAA),which can theoretically guarantee that all cover states of vertices converging in an SNE with polynomial time.Subsequently,we improve the GAA by adding 2-hop and 3-hop adjustment mechanisms,termed the improved game-based asynchronous algorithm(IGAA),in which we prove that it can obtain a better solution to the WVC problem than using a the GAA.Finally,numerical simulations demonstrate that the proposed IGAA can obtain a better approximate solution in promising computation time compared with the existing representative algorithms.

Solving the Balance Problem of On-Line Role-Playing Games Using Evolutionary Algorithms

In on-line role-playing games (RPG), each race holds some attributes and skills. Each skill contains several abilities such as physical damage, hit rate, etc. Parts of the attributes and all the abilities are a function of the character’s level, which are called Ability-Increasing Functions (AIFs). A well-balanced on-line RPG is characterized by having a set of well-balanced AIFs. In this paper, we propose an evolutionary design method, including integration with an improved Probabilistic Incremental Program Evolution (PIPE) and a Cooperative Coevolutionary Algorithm (CCEA), for on-line RPGs to maintain the game balance. Moreover, we construct a simplest turn-based game model and perform a series of experiments based on it. The results indicate that the proposed method is able to obtain a set of well-balanced AIFs efficiently. They also show that in this case the CCEA outperforms the simple genetic algorithm, and that the capability of PIPE has been significantly improved through the improvement work.

A Competitive Markov Approach to the Optimal Combat Strategies of On-Line Action Role-Playing Game Using Evolutionary Algorithms

In the case of on-line action role-playing game, the combat strategies can be divided into three distinct classes, Strategy of Motion(SM), Strategy of Attacking Occasion (SAO) and Strategy of Using Skill (SUS). In this paper, we analyze such strategies of a basic game model in which the combat is modeled by the discrete competitive Markov decision process. By introducing the chase model and the combat assistant technology, we identify the optimal SM and the optimal SAO, successfully. Also, we propose an evolutionary framework, including integration with competitive coevolution and cooperative coevolution, to search the optimal SUS pair which is regarded as the Nash equilibrium point of the strategy space. Moreover, some experiments are made to demonstrate that the proposed framework has the ability to find the optimal SUS pair. Furthermore, from the results, it is shown that using cooperative coevolutionary algorithm is much more efficient than using simple evolutionary algorithm.

A Game Theoretic Approach for a Minimal Secure Dominating Set

The secure dominating set(SDS),a variant of the dominating set,is an important combinatorial structure used in wireless networks.In this paper,we apply algorithmic game theory to study the minimum secure dominating set(Min SDS) problem in a multi-agent system.We design a game framework for SDS and show that every Nash equilibrium(NE) is a minimal SDS,which is also a Pareto-optimal solution.We prove that the proposed game is an exact potential game,and thus NE exists,and design a polynomial-time distributed local algorithm which converges to an NE in O(n) rounds of interactions.Extensive experiments are done to test the performance of our algorithm,and some interesting phenomena are witnessed.

Anti-jamming channel access in 5G ultra-dense networks: a game-theoretic learning approach

This paper investigates the Quality of Experience(QoE)oriented channel access anti-jamming problem in 5th Generation Mobile Communication(5G)ultra-dense networks.Firstly,considering that the 5G base station adopts beamforming technology,an anti-jamming model under Space Division Multiple Access(SDMA)conditions is proposed.Secondly,the confrontational relationship between users and the jammer is formulated as a Stackelberg game.Besides,to achieve global optimization,we design a local cooperation mechanism for users and formulate the cooperation and competition among users as a local altruistic game.By proving that the local altruistic game is an Exact Potential Game(EPG),we further prove the existence of pure strategy Nash Equilibrium(NE)among users and Stackelberg Equilibrium(SE)between users and jammer.Thirdly,to obtain the equilibrium solutions of the proposed games,we propose an anti-jamming channel selection algorithm and improve its convergence speed through heterogeneous learning parameters.The simulation results validate the convergence and effectiveness of the proposed algorithm.Compared with the throughput optimization scheme,our proposed scheme obtain a greater network satisfaction rate.Finally,we also analyze user fairness changes during the algorithm convergence process and get some interesting conclusions.

A Review of the Current Task Offloading Algorithms,Strategies and Approach in Edge Computing Systems

Task offloading is an important concept for edge computing and the Internet of Things(IoT)because computationintensive tasksmust beoffloaded tomore resource-powerful remote devices.Taskoffloading has several advantages,including increased battery life,lower latency,and better application performance.A task offloading method determines whether sections of the full application should be run locally or offloaded for execution remotely.The offloading choice problem is influenced by several factors,including application properties,network conditions,hardware features,and mobility,influencing the offloading system’s operational environment.This study provides a thorough examination of current task offloading and resource allocation in edge computing,covering offloading strategies,algorithms,and factors that influence offloading.Full offloading and partial offloading strategies are the two types of offloading strategies.The algorithms for task offloading and resource allocation are then categorized into two parts:machine learning algorithms and non-machine learning algorithms.We examine and elaborate on algorithms like Supervised Learning,Unsupervised Learning,and Reinforcement Learning(RL)under machine learning.Under the non-machine learning algorithm,we elaborate on algorithms like non(convex)optimization,Lyapunov optimization,Game theory,Heuristic Algorithm,Dynamic Voltage Scaling,Gibbs Sampling,and Generalized Benders Decomposition(GBD).Finally,we highlight and discuss some research challenges and issues in edge computing.

Non-Cooperative Game of Coordinated Scheduling of Parallel Machine Production and Transportation in Shared Manufacturing

Given the challenges of manufacturing resource sharing and competition in the modern manufacturing industry,the coordinated scheduling problem of parallel machine production and transportation is investigated.The problem takes into account the coordination of production and transportation before production as well as the disparities in machine spatial position and performance.A non-cooperative game model is established,considering the competition and self-interest behavior of jobs from different customers for machine resources.The job from different customers is mapped to the players in the game model,the corresponding optional processing machine and location are mapped to the strategy set,and the makespan of the job is mapped to the payoff.Then the solution of the scheduling model is transformed into the Nash equilibrium of the non-cooperative game model.A Nash equilibrium solution algorithm based on the genetic algorithm(NEGA)is designed,and the effective solution of approximate Nash equilibrium for the game model is realized.The fitness function,single-point crossover operator,and mutation operator are derived from the non-cooperative game model’s characteristics and the definition of Nash equilibrium.Rules are also designed to avoid the generation of invalid offspring chromosomes.The effectiveness of the proposed algorithm is demonstrated through numerical experiments of various sizes.Compared with other algorithms such as heuristic algorithms(FCFS,SPT,and LPT),the simulated annealing algorithm(SA),and the particle swarm optimization algorithm(PSO),experimental results show that the proposed NE-GA algorithm has obvious performance advantages.

Coordinated Scheduling of Two-Agent Production and Transportation Based on Non-Cooperative Game

A two-agent production and transportation coordinated scheduling problem in a single-machine environment is suggested to compete for one machine from different downstream production links or various consumers.The jobs of two agents compete for the processing position on a machine,and after the pro-cessed,they compete for the transport position on a transport vehicle to be trans-ported to two agents.The two agents have different objective functions.The objective function of the first agent is the sum of the makespan and the total trans-portation time,whereas the objective function of the second agent is the sum of the total completion time and the total transportation time.Given the competition between two agents for machine resources and transportation resources,a non-cooperative game model with agents as game players is established.The job pro-cessing position and transportation position corresponding to the two agents are mapped as strategies,and the corresponding objective function is the utility func-tion.To solve the game model,an approximate Nash equilibrium solution algo-rithm based on an improved genetic algorithm(NE-IGA)is proposed.The genetic operation based on processing sequence and transportation sequence,as well as the fitness function based on Nash equilibrium definition,are designed based on the features of the two-agent production and transportation coordination scheduling problem.The effectiveness of the proposed algorithm is demonstrated through numerical experiments of various sizes.When compared to heuristic rules such as the Longest Processing Time first(LPT)and the Shortest Processing Time first(SPT),the objective function values of the two agents are reduced by 4.3%and 2.6% on average.

飞行器博弈制导进程与展望

博弈制导可处理复杂系统中涉及多方合作、竞争的动态问题,有利于实现智能化战场上信息价值最大化发挥,推动精确制导武器的智能化发展。本文总结了博弈制导的基本分类和建模方法,从终端角度约束、时间约束、过载约束、末速约束等方面提出了飞行器博弈制导的关键性问题,搭建了矩阵博弈、微分博弈两种典型博弈模型求解框架,从解析解、数值解、智能算法等方面对博弈制导的求解方法进行梳理。最后,从非线性微分博弈求解方法,非完备信息博弈算法,不均衡、非对称信息下多飞行器协同,多类型武器体系博弈等方向出发,对飞行器博弈制导未来的发展趋势进行了展望和总结。

基于随机博弈与A3C深度强化学习的网络防御策略优选

网络资源的有限性和攻防对抗的动态性导致最优防御策略难以选取,将深度强化学习引入攻防随机博弈建模领域,通过构建网络攻防actor策略网络和critic价值网络,结合随机博弈模型构建了网络攻防博弈决策模型总体结构,在此基础上引入异步优势演员评论家算法(asynchronous advantage actor-critic,A3C)智能体学习框架设计了防御策略选取算法;针对现有方法未考虑攻击方群体间的共谋攻击,引入群智能体性格特征,建立合作系数μ来刻画攻击者之间的合作对攻防策略收益的影响,进而得出对防御策略选取的影响,构建的博弈决策模型更符合攻防实际情况。实验结果表明,该方法的策略求解速度要优于现有方法,同时由于考虑了攻击合作关系,能够用于分析攻击者群体间合作关系对防御者决策的影响,防御策略选取更有针对性,期望防御收益更高。

非合作博弈背景下基于BSA的配电网优化重构

为缓解分布式电源大规模接入对配电网安全稳定运行的影响,提出一种考虑分布式电源输出功率的不确定性的有源配电网优化重构方法.首先,采用非合作博弈理论研究电网调度人员与“大自然”之间的博弈关系,将配电网系统中光伏单元的不确定性视为“大自然”博弈方;其次,以有功网损、负荷均衡度、电压偏差最小为目标函数,建立有源配电网优化重构模型,通过回溯搜索算法(backtracking search algorithm,BSA)进行迭代求解,得到最优重构方案;最后,在IEEE33节点系统进行仿真分析,验证模型的正确性及求解算法的有效性.研究结果表明,相较传统重构方法,本文方法更充分考虑了分布式电源输出功率的不确定性,并且在最恶劣的情况发生时,得到的重构策略能够使配电网系统的有功网损、负荷均衡度、电压偏差指标分别降低0.31%、0.59%、0.48%.

基于改进灰狼算法的微网多主体主从博弈策略

为平衡包含电、热两种能源形式的微网系统内各参与者间的利益关系,通过改进灰狼算法提出了一种微网能量管理模型。首先,在充分分析微网结构及其各主体功能的基础上,为综合考虑源-网-荷的决策能力,将主从博弈方法应用于产能商、微网运营商、负荷聚合商之间的互动,建立一主多从的微网能量管理数学模型;其次,针对博弈上层模型高维、非线性的特点,在传统灰狼算法基础上,利用Tent映射对种群进行初始化、采用非线性收敛因子平衡种群搜索能力、利用莱维飞行策略降低陷入局部最优的风险。在模型求解时,博弈上层采用改进灰狼算法,下层采用二次规划方法,二者结合以探讨使各主体利益最大的策略;最后,通过算例进行验证,结果表明:本文算法更加高效,所提模型在提高参与者收益,平滑用户负荷分布方面更加优越。