基于遗传算法的方法解决皇后区的最小支配集问题

文摘

领域的计算、组合和相关领域,研究人员制定几个皇后问题的最小支配集的技术(MDSQP)属于典型的棋盘游戏。然而,文献表明,有限的研究进行了解决MDSQP使用bioinspired算法。为了填补这一空缺,本文提出了基于遗传算法的简单而有效的解决方案来解决这个经典问题。我们报告的结果,证明了最优解附近已经由GA不同大小的董事会从8×8到11×11。

1。介绍

或称为国际象棋的MDSQP覆盖问题是一个著名的棋盘的问题已经被研究者接受持续的利益包括计算智能领域。图论领域,特别是控制集的研究解决这个问题甚至在1970年代早期。在棋盘,细胞组织行和列。国际象棋门外汉来说,女王(说)放在广场将成为所有广场相关的行,列,和两个对角线参照。这个问题背后的想法是找到所需的最小数量的皇后主导整个棋盘。统治这里指的是覆盖所有可能的广场被攻击的皇后区包括广场由各自的皇后。之前的研究一直试图找到控制号码为皇后问题用数学和组合方法(1- - - - - -8]。许多公式推导,介绍了这些方法。已经观察到有限的努力进行了采用进化算法来解决MDSQP。事实上,大多数的研究在文献中是致力于解决原始- - - - - -皇后问题叫做nonattacking问题。这些研究的结果表明,进化算法能够回溯等优于其他原则方法解决此类问题。然而,这些研究只关注nonattacking皇后问题,而我们所知,MDSQP已经至少考虑使用bioinspired进化算法。

进化算法已被证明是成功的求解和优化包括组合在内的一系列复杂问题,如一个研究,在合理的计算时间内(9]。一般来说,进化算法可以分为两大类,基于群体智能方法和古典进化方法。群体智慧(SI)方法启发社会自然行为,如动物的群体行为时寻找食物或避免某些威胁(10]。几个SI方法参照文献包括粒子群优化(PSO)和蚁群优化(ACO)。算法已被证明有效的解决一些优化问题(11]。算法也展示了好的结果优化供应链管理等各种复杂问题(例如,12])和最短路径问题[13,14]。

经典进化算法,另一方面,包括遗传算法,成功地采用各种优化问题。遗传算法是一种最常用的进化算法在文献中在1970年代首次提出(15]。GA自然过程的启发搜索和选择过程导致适者生存个人(15]。文献的研究人员已经证明了采用遗传算法在解决各种优化的效率问题,如数据挖掘(16)和网络流量控制(17]。事实上,采用遗传算法在文献中完全解决一些问题,如(17,18),杂化与其他方法更加强的结果。通常,GA杂化与当地和启发式搜索方法如布谷鸟搜索(19和禁忌搜索20.]。此外,不同的研究人员杂化与其他进化方法如动态规划(21]。

因此,本文打算填补这些空白和现在bioinspired遗传算法(GA)解决MDSQP问题通过考虑董事会规模逐渐的典型棋盘上的一个董事会。该方法逐渐增加的数量皇后放在董事会从下界以下建议在文献中,直到被确定(即最优的解决方案。,所有的方格棋盘为主)。剩下的纸是组织如下:部分2讨论了相关工作;部分3制定问题;部分4介绍了拟议的技术的进化机制;结果讨论部分5最后本文总结与未来工作见解部分6。

2。相关工作

大量的努力一直致力于研究棋盘问题。棋盘问题主要是分类皇后问题和控制设置(即。覆盖问题)。最初的皇后问题可以定义为将女王在棋盘以最优的方式,如没有皇后应该相互攻击22,23]。它在1850年首次引入24]。许多研究已经进行使用不同的方法来解决这个问题;他们中的大多数采用数学方法和图论等(25- - - - - -27]。研究这样的问题可能受益的理解各种应用,如交通管制、死锁预防和并行存储器(28]。的复杂性皇后问题被称为指数,它变得更加复杂的大值。采用各种方法来解决这个问题,比如回溯(29日),神经网络(30.- - - - - -32),进化优化算法(33- - - - - -42]。

支配集问题另一方面由计算机科学研究人员尚未引起足够的关注。事实上,各种研究已经致力于探讨这样一个问题,但主要是采用数学模型。汉堡和Mynhardt指出女王统治的问题是一个最困难的棋盘问题[43]。它通常被定义为寻找所需的最低数量的皇后区涵盖所有的方块棋盘。这个数字称为统治编号和引用的符号。研究人员已经抵达上界和下界自1970年代初(3]。许多配方和价值观被派生,发现特别是小的值(3,43- - - - - -45]。表1显示这些值。图1显示了一个典型的棋盘问题的简要分类。例如,进行了几项研究发现控制数量的正常统治(8]。在这些研究中,需要找到最佳放在最低皇后区棋盘覆盖所有方块的董事会。然而,许多研究人员认为支配集问题下几个变化。为例,进行了许多研究探讨独立支配数可定义为皇后不相互攻击的数量和覆盖整个棋盘(3]。不同的价值观和公式推导,证明在数学上下文中。此外,“对角女王统治问题”是经常在文学。在这样一个问题,需要找到最低的数量皇后放置在主对角线和覆盖整个棋盘(3,4]。安乐乡也试图找到女王的统治号码放在单个列(3]。此外,许多研究人员进行研究,以解决问题的控制设置在一个环形棋盘(1]。在这样的研究中,应找出最小数量的皇后区,覆盖整个广场环面。Bozoki et al .,另一方面,揭示不同的问题称为“统治皇后区的矩形图”,它需要找到女王的统治数量在一个矩形棋盘(),广场的数量列和行是不同的(46]。他们为小值派生的下界和特别是。

如上所述,皇后支配集问题已经极大地研究尤其是使用数学方法。然而,文学仍然缺乏计算模型的采用特别优化的方法来解决这个问题。有限的文章被发现技术上考虑这个问题。例如,Fernau试图使用回溯分析这个问题的复杂性,在子集动态规划,动态规划路径分解(47]。他表示,控制女王的复杂性问题是一个具有挑战性的问题。另一方面,Mohabbati-Kalejahi et al。(2012)提出了一个混合的帝国主义竞争算法(ICA),本地搜索算法为了解决基于nonattacking女王的统治问题[48]。提出的混合算法与基本ICA的两个问题,结果表明改进的性能而言,平均运行时和平均健身价值。解决方案是nonattacking制定皇后问题。然而,对于统治的问题更少的细节和信息提供了关于该算法的实现细节。例如,关键组件的进化算法,如制定一个适应度函数没有详细介绍。因此,这项工作的目的是填补这一空缺在文献中采用典型bioinspired遗传算法(GA)来解决皇后问题的最小支配集(MDSQP)。该算法在以下部分中描述。

3所示。问题公式化

为了解决这个问题,它以编程方式我们首先标记所有方格棋盘的测序数据逐渐从1开始从最左广场底部右最顶部广场。图2显示了一个示例的模式参照常用的标签棋盘。此外,所有方块在董事会有一个位置(类似于解析几何的规范)坐标形式,表示行数和列号表示。例如,广场的位置在图282(4,4)。这个位置可以用来确定主导方块皇后放置在一个特定的广场。让是一组棋盘方格,让由女王的主要广场的情况下皇后区的数量。然后接下去 这个问题首先需要定义一个适应度函数定义一个方法来识别主导方块皇后在黑板上。皇后的位置一个平方将如果至少有下列条件之一: 方程(2)和(3)代表主导广场的行和列,分别。其余的方程(4)(7)代表广场由放置在女王的对角线方向。特别是主导正方形的两条对角线与四方(左上、左下、右上、右下)。例如,广场19日10日和1在图2是主导广场的实例由女王放在广场28,这种情况下建模使用逻辑代数表达式使用(4)。主要目标是最大化的方格棋盘的主导皇后区和寻找最佳的地点皇后区是相当具有挑战性由于排列和组合的复杂性。因此,这是衡量以下适应度函数: 在哪里 这个函数趋于1的价值当所有的方格的棋盘得到至少一次主导。换句话说,一个健身值< 1可以团结地表明有一些方块或者至少1平方没有被任何主导th(女王)。

4所示。配方使用遗传算法的问题

拟议的GA配方建模来解决棋盘。提出了遗传算法的整体结构可以在图进行描述3。

4.1。编码

个人在一个矩阵编码的顺序。直观地行和列的产物,代表了人口规模(许多可能的候选人的解决方案)。矩阵的元素表示位二进制编码的标签(每平方贴上之前讨论)的皇后被放在棋盘上。下面的矩阵显示的几个典型例子可能的候选人的解决方案 此外,主导广场也被编码在一个矩阵如下所示;独特的总数主导广场为代表的行数。 上述矩阵给出了一个示例实例包含两个正方形的一组主导的棋盘。此外,让我们假设我们想只编码一个候选人在一个解决方案棋盘。图3显示两个皇后放在广场贴上6和16。通过将这些方块的十进制值转换为8位二进制代码和考虑有两个皇后,因此,我们得到一个矩阵如下所示: 此外,确定主导广场由两个皇后放在棋盘上,(2)(7必须应用)。因此,图3显示所有方格棋盘除了标签3是由两个皇后。因此,控制集如下: 转换的元素到八位二进制代码,我们将得到以下主要集矩阵:

典型的交叉操作的说明如下:

4.2。初始种群和健康评估

随机的人口由100人组成的(可能的候选人的解决方案)是在遗传算法的初始化阶段生成确保皇后区被放置在不同的广场上。女王的统治率是使用适应度函数计算的部分建模2。我们提出的技术的选择标准如下。个人分类是基于他们的健身价值和最富有的50%的人口(与潜在候选人健身能力)可以生存,会考虑到下一代。候选人的健身能力低于50%会被丢弃(他们将不允许生存)。随后这个选择过程,经典的采用轮盘赌选择方法选择个人,将交配繁殖。

4.3。交叉和后代一代

新一代是由两个父母之间实现一点交叉。该交叉算子所涉及的步骤可以描述如下:(我)两个人选择根据选择操作符。(2)生成一个随机的交叉点在两个父母。(3)交叉点后交换遗传物质。(iv)验证新个体,个体被保留在棋盘的边界内。(v)如果一个后代的位置恰好为零由于推断统计学,生成一个随机的调整点。(vi)改变调整位置的值为1。(七)如果一个后代的位置比根据棋盘大小改变染色体的位数的值导致这个问题为0。方程 显示了一个示例双亲之间的交叉操作产生的两个孩子(后代); 交叉操作的显示了一个示例来说明验证和调整的过程。

此外,我们还实现突变的概率为0.05。在突变,我们只需选择两个随机位置选择的个人和替代这些位置的值补充(即。,改变0到1,反之亦然)。为了避免个人的生产边界以外的棋盘上,发现了相同的交叉验证和调整机制是有效的。

5。实验和结果

提出的遗传算法使用MATLAB实现,尝试使用一个2.6 Ghz PC与微软与英特尔i5处理器安装启用Windows 8操作系统。这是独立测试使用不同的棋盘的大小从常见的棋盘的大小来在每个测试实例皇后放在棋盘的数量逐渐增加从下界在文献中报道,直到最大的健身。此外,提出了遗传算法是迭代1000次为每个实例和最好的健身价值记录。这个贡献的结果报告在运行遗传算法为每个测试实例五倍。表2显示了最大的一个总结健身GA的价值达成的来以及女王数字放在棋盘上。获得的结果是有前途和接近MDSQP上界的文献报道。

它可以注意到GA可以覆盖的88%和95%棋盘放置三个和四个皇后,分别。GA也能够找到最优解相同大小的董事会在放置五皇后区这意味着支配的棋盘是5(也就是,)。这些研究结果比较和文献中报道的结果。提出的遗传算法被认为是一个先锋文学考虑MDSQP,结果将与文学中的值已被派生的数学。表3显示最优控制数字GA相比,这些获得的。表2也表明,遗传算法能够主宰的99%棋盘当五皇后区被放置在董事会,尽管五派生的支配数量棋盘)。然而,达成的一个最佳的解决方案是越来越多的皇后放在董事会6)(见表3)。同样,五报道数量控制的情况下和棋盘;然而,遗传算法无法覆盖整个董事会。事实上,只有95%的董事会时覆盖和五个皇后放置()(见表2)。比例控制已得到改进略当添加一个女王()董事会。然而,一个最优的解决方案被发现在放置七皇后区董事会的情况= 10,11)。所有解决方案产生的图形化模拟的遗传算法结束时执行。图4显示了模拟与拟议中的遗传算法的最优解的情况到11个。红圈(点)代表女王和蓝色的圆圈代表典型的主要广场棋盘。它也显示了健身价值相对应的提出解决方案的生成解决方案的数量。此外,提出了遗传算法的解决方案的性能测量后的执行每个测试实例。结果表明,性能的健身价值越来越多的迭代。由于空间限制,我们现在的性能结果棋盘图5。它显然可以观察到健身值在所有的情况下提高了迭代往往接近上限。

可以看出,提出的解决方案产生了技术能产生良好的控制性能(95%对99%)即使对于大板尺寸,特别是为例和。

6。结论

在本文中,我们提出了一个遗传算法(GA)的基础技术解决经典皇后问题的最小支配集(MDSQP)。实验结果表明,提出的基于遗传算法的解决方案是能够找到最优接近最优解决方案甚至大尺寸的板(和)。对于一个典型的例子棋盘,建议的解决方案产生了一个完美的最优解与文献中报道的解决方案。此外,实验结果还系统地证明平均健身价值接近最大在后续迭代中。这些结果将为我们未来的工作,我们打算部署其他bioinspired计算技术,如膜计算。

的利益冲突

作者宣称没有利益冲突。

引用

1. 答:汉堡、c . Mynhardt和w·d·Weakley”统治的环形皇后区图大小3 k x 3 k,”澳大拉西亚的《组合28卷,第148 - 137页,2003年。视图:谷歌学术搜索
2. a . p .汉堡和c . m . Mynhardt”,一种改进的上界为女王统治数字,”离散数学,卷266,不。1 - 3、119 - 131年,2003页。视图:出版商的网站|谷歌学术搜索|MathSciNet
3. e . j .安乐乡”棋盘统治问题。”《离散数学卷,48 13-20,1991页。视图:出版商的网站|谷歌学术搜索
4. e . j .安乐乡,s . t . Hedetniemi对角线上女王统治问题。”组合理论,杂志系列,42卷,不。1,第139 - 137页,1986。视图:出版商的网站|谷歌学术搜索|MathSciNet
5. t . Kikuno:吉田,y Kakuda”统治的线性算法串并联图,“离散应用数学,5卷,不。3、299 - 311年,1983页。视图:出版商的网站|谷歌学术搜索|MathSciNet
6. a . Klobučar”统治的红衣主教产品P_6×P_n,”数学交流,4卷,不。2、241 - 250年,1999页。视图:谷歌学术搜索
7. n纱丽和d . IH的奥古斯汀•统治的一些图形操作,2016年。
8. 文卡特斯和Venkatesan年代。,“Tight lower bounds for connected queen domination problems on the chessboard,”https://arxiv.org/abs/1608.02531。视图:谷歌学术搜索
9. b·杜尔a . Eremeev c . Horoba f·诺伊曼和m . Theile“进化算法和动态规划”《第11届会议上遗传与进化计算ACM,页771 - 778年,魁北克,加拿大,2009。视图:谷歌学术搜索
10. m . Mavrovouniotis c·李、杨,“动态优化的调查群体智慧:算法和应用,“群与进化计算33卷,1卷,2017页。视图:谷歌学术搜索
11. d . Karaboga b . Gorkemli c Ozturk, n . Karaboga”全面调查:人工蜂群(ABC)算法和应用,“人工智能审查,42卷,21-57,2014页。视图:出版商的网站|谷歌学术搜索
12. r . s . Kadadevaramath j·c·h·陈,b . l . Shankar和k . Rameshkumar”应用粒子群智能算法在供应链网络结构优化、”专家系统与应用程序,39卷,不。11日,第10176 - 10160页,2012年。视图:出版商的网站|谷歌学术搜索
13. A . Migdalas y Marinakis, A . Sifaleras”混合粒子群optimization-variable约束最短路径问题的邻域搜索算法,”欧洲运筹学杂志》上,卷261,不。3、819 - 834年,2017页。视图:出版商的网站|谷歌学术搜索|MathSciNet
14. m . Akhand s·侯赛因,akt,”著名的基于粒子群优化方法的比较研究来解决旅行商问题,“国际期刊的群体智慧和演化计算,5卷,不。139年,p . 2016。视图:谷歌学术搜索
15. m·斯和l . m . Patnaik”遗传算法:一项调查,”电脑,27卷,不。6,17-26,1994页。视图:出版商的网站|谷歌学术搜索
16. d . e . Goldberg和j . h .荷兰“遗传算法和机器学习,”机器学习,3卷,不。2 - 3、95 - 99年,1998页。视图:出版商的网站|谷歌学术搜索
17. A . Barolli m . Takizawa f . Xhafa, l . Barolli”应用遗传算法在移动ad hoc网络QoS路由:一项调查,”诉讼的第五届国际会议上宽带无线计算、通信和应用程序(BWCCA 10)259年,页250 - 2010年11月,日本福冈。视图:出版商的网站|谷歌学术搜索
18. b . m . Varghese和r . j . s . Raj”调查变异的遗传算法调度工作流的任务”第二届国际会议在科学技术工程和管理(ICONSTEM 16),2016年。视图:谷歌学术搜索
19. A . Abu-Srhan和e·艾尔·达乌德”,使用遗传算法和混合算法布谷鸟搜索算法解决旅行商问题及其应用到多个序列比对,“国际先进的科学和技术杂志》上卷。61年,第29,2013页。视图:谷歌学术搜索
20. a . m . Allakany t·m·马哈茂德·k·冈村和m . r . Girgis”多个QoS约束多播路由优化算法基于遗传禁忌搜索算法,”计算机科学的进步,4卷,不。3,2015。视图:谷歌学术搜索
21. d·t·范教授t . t . b .黄齐,t . l .中方“调查组合遗传算法和动态规划解决旅行商问题,”学报》国际会议软计算和模式识别(SoCPaR 13)河内,页66 - 71年,越南,2013年12月。视图:出版商的网站|谷歌学术搜索
22. Rivin,即瓦迪和p·齐默尔曼,”$n$皇后问题。”美国数学月刊,卷101,不。7,629 - 639年,1994页。视图:出版商的网站|谷歌学术搜索|MathSciNet
23. 并与r·迪克森”$n$皇后问题。”离散数学,12卷,不。4、393 - 395年,1975页。视图:出版商的网站|谷歌学术搜索|MathSciNet
24. c . Letavec和j·鲁杰罗”n皇后问题。”通知教育事务,卷2,不。3、101 - 103年,2002页。视图:谷歌学术搜索
25. r . Sosic和j .顾”3000000皇后在不到一分钟。”ACM SIGART公告,卷2,不。2、22 - 24,1991页。视图:谷歌学术搜索
26. m·r·恩格尔哈特的“基于群体搜索的解决方案$n$皇后问题。”离散数学,卷307,不。21日,第2551 - 2535页,2007年。视图:出版商的网站|谷歌学术搜索|MathSciNet
27. z Szaniszlo、m . Tomova和c . Wyels”$N$皇后问题对称托普利兹矩阵”,离散数学,卷309,不。4、969 - 974年,2009页。视图:出版商的网站|谷歌学术搜索|MathSciNet
28. j·贝尔和b·史蒂文斯“的调查结果和研究领域$n$皇后。”离散数学,卷309,不。1日至31日,2009页。视图:出版商的网站|谷歌学术搜索|MathSciNet
29. r . Sosič和j·顾”,有效的本地搜索与冲突最小化:一个案例研究的n-queens问题,“IEEE工程知识和数据》第六卷,没有。5,661 - 668年,1994页。视图:出版商的网站|谷歌学术搜索
30. t .郭和k·a·史密斯,”实验分析混沌神经网络模型的组合优化一个统一的框架下,“神经网络,13卷,不。7,731 - 744年,2000页。视图:出版商的网站|谷歌学术搜索
31. n . Funabiki y竹中平藏,s . Nishikawa“最大N-queens问题的神经网络方法,”生物控制论,卷76,不。4、251 - 255年,1997页。视图:出版商的网站|谷歌学术搜索
32. j . Mandziuk和b . Macuk神经网络旨在解决N-queens问题,“生物控制论,卷66,不。4、375 - 379年,1992页。视图:出版商的网站|谷歌学术搜索
33. d . z . Wang黄,j . Tan t . Liu k .赵和l·李,“解决n-queens问题的并行算法基于计算模型的启发,“生物系统卷,131年11月,2015页。视图:出版商的网站|谷歌学术搜索
34. a . Maroosi和r . c . Muniyandi“加速执行P与活跃的膜系统解决$N$皇后问题。”理论计算机科学卷。551年,39-54,2014页。视图:出版商的网站|谷歌学术搜索|MathSciNet
35. r . Maazallahi A . Niknafs, p . Arabkhedri。”一个多项式时间的dna计算解决方案n皇后问题。”Procedia-Social和行为科学卷,83年,第628 - 622页,2013年。视图:谷歌学术搜索
36. 臂形韵律层,s . Meshoul h . Talbi和m . Batouche量子激发微分进化算法所解决N皇后问题。”神经网络,卷1,p . 2011。视图:谷歌学术搜索
37. b . Keswani使用Meta-Heuristic算法实现n-Queens拼图(布谷鸟搜索)(论文)Suresh吉安Vihar大学出版社,2013年。
38. a·a·谢赫a .沙k .阿里和a·h·s·布哈里”粒子群优化N皇后问题。”先进的计算机科学与技术杂志》上,1卷,不。2,页57 - 63,2012。视图:谷歌学术搜索
39. j·e·a·赫利斯和m . a . Oskoei“改进遗传算法求解n-queens问题”诉讼伊朗智能会议系统(艾多酷的14),伊朗巴姆地震,2014年2月。视图:出版商的网站|谷歌学术搜索
40. 汗,m . Bilal m·谢里夫m . Sajid r·贝格,“使用ACO n-Queen问题的解决方案,”IEEE学报》13日国际Multitopic会议(INMIC ' 09)IEEE,页1 - 5,伊斯兰堡,巴基斯坦,2009年12月。视图:出版商的网站|谷歌学术搜索
41. n .沃恩“交换算法和meta-heuristic解决方案组合优化n-queens问题,”《科学和信息会议(SAI的15),页102 - 104,伦敦,英国,2015年7月。视图:出版商的网站|谷歌学术搜索
42. e . Masehian h . Akbaripour和n . Mohabbati-Kalejahi”景观分析和有效的解决metaheuristics$n$皇后问题。”计算优化和应用程序卷,56号3、735 - 764年,2013页。视图:出版商的网站|谷歌学术搜索|MathSciNet
43. a . p .汉堡和c . m . Mynhardt“上界最小数量的皇后区覆盖$n\times n$棋盘上。”离散应用数学,卷121,不。1 - 3,51-60,2002页。视图:出版商的网站|谷歌学术搜索|MathSciNet
44. w·d·Weakley“上界控制数量的女王的图表,“离散数学,卷242,不。1 - 3、229 - 243年,2002页。视图:出版商的网站|谷歌学术搜索|MathSciNet
45. p·吉本斯和j·韦伯,”女王统治的一些新结果的问题,”澳大拉西亚的《组合15卷,第160 - 145页,1997年。视图:谷歌学术搜索
46. s . Bozoki p .加、i Marosi和w·d·Weakley“矩形女王统治的图,https://arxiv.org/abs/1606.02060。视图:谷歌学术搜索
47. h . Fernau,”皇后的最小支配集:一个微不足道的编程练习?”离散应用数学,卷158,不。4、308 - 318年,2010页。视图:出版商的网站|谷歌学术搜索|MathSciNet
48. n . Mohabbati-Kalejahi h . Akbaripour,大肠Masehian”基本和混合帝国主义竞争算法求解非攻击性和non-dominating n-queens问题,”计算智能:国际联合会议,IJCCI 2012年巴塞罗那,西班牙,2012年10月5日至7日,修改选定的论文,k . Madani公元科雷亚是a .罗莎和j·菲利浦- Eds。施普林格,页79 - 96年,2015年。视图:谷歌学术搜索

版权

版权©2017 Saad Alharbi和易卜拉欣引导。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。