Studies in Computational Intelligence 427 Editor-in-Chief Prof.JanuszKacprzyk SystemsResearchInstitute PolishAcademyofSciences ul.Newelska6 01-447Warsaw Poland E-mail:[email protected] Forfurthervolumes: http://www.springer.com/series/7092 Xin-She Yang (Ed.) Artificial Intelligence, Evolutionary Computing and Metaheuristics In the Footsteps of Alan Turing ABC Editor Xin-SheYang NationalPhysicalLaboratory MathematicsandScientificComputing Teddington UK ISSN1860-949X e-ISSN1860-9503 ISBN978-3-642-29693-2 e-ISBN978-3-642-29694-9 DOI10.1007/978-3-642-29694-9 SpringerHeidelbergNewYorkDordrechtLondon LibraryofCongressControlNumber:2012936118 (cid:2)c Springer-VerlagBerlinHeidelberg2013 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped.Exemptedfromthislegalreservationarebriefexcerptsinconnection with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’slocation,initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer. PermissionsforusemaybeobtainedthroughRightsLinkattheCopyrightClearanceCenter.Violations areliabletoprosecutionundertherespectiveCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Whiletheadviceandinformationinthisbookarebelievedtobetrueandaccurateatthedateofpub- lication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityforany errorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,withrespect tothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) To AlanTuring Preface Alan Turing pioneered many research areas from artificial intelligence to com- putability, from cryptography to heuristics and from Fabonacci phyllotaxis to patternformation.Hehadworkedinmanyprestigiousinstitutions,includingCam- bridgeUniversity,PrincetonUniversity,NationalPhysicalLaboratory,andManch- esterUniversity.2012istheAlanTuringyear–a centenarycelebrationofthelife andworkofAlanTuring. In 1945, Turing was recruited to the National Physical Laboratory (NPL), UK where he set out his design for the Automatic Computing Engine (ACE). During thistime,helivedatHighStreet,Hampton,RichmonduponThameswhereablue plaque is still visible on that street. In an NPL report on Intelligent machinery in 1948,heoutlinedhisinnovativeideasofmachineintelligenceandlearning,neural networksandevolutionaryalgorithms.Thislittleknownreporthadinfactinspired awiderangeofresearchareas. Nowadays at the information age, it is hard to imagine how the world would be without computers and the Internet, in addition to many other crucial things. Without Turing’s work, especially the “Turing Machine” concept at the heart of everycomputerandmicrochiptoday,somanythingsonwhichwearesodependent wouldnotbepossible.Nowonderthereareaseriesofimportanteventsworldwide this year to celebrate the life and work, the far-reaching legacy of Alan Turing. Forexample,oneofthemostprestigiousjournalNatureeditedaspecialcollection Turing at 100:Legacy of a Universal Mind in Februarythis year. Meanwhile,the TuringCentenaryConference:HowtheWorldComputeswillbeheldatCambridge Universitycoincideswiththe100thBirthdayofAlanTuring. To celebrate Turing’s legacy and to follow the footsteps of this brilliant mind, we take this golden opportunity in the 2012 Turing year to review the latest de- velopments in areas of artificial intelligence, evolutionary computation and meta- heuristics, and all these areas can be traced back to Turing’s pioneer work. The responses to our call of celebration were overwhelming,we have received a huge number of high quality contributions. As the limitation of the space of this book, wehavetochooseovertwodozenpaperswhilingleavingmanyhigh-qualitypapers notincludedinthisbook.Wetriedtomainabalanceintopicscoverage,relevance VIII Preface to Turing’swork, and state of the art. Amongour contributorsto this book,many are world-leading experts in their areas. Their reviews and contributionsnot only provideatimelysnapshotofthestate-of-artdevelopments,butalsoprovideinspira- tionforyoungresearcherstocarryoutpotentiallyground-breakingresearchinthese active,diverseresearchareas. UnintentionallyfollowingthefootstepsofAlanTuring,Iwasfortunateenough, afewyearsago,tomovefromCambridgeUniversitytojoinNationalPhysicalLab- oratorytoworkasaSeniorResearchScientistatMathematicsandScientificCom- puting where Alan Turing had worked. Turing has been one of major influences onmyresearchconcerningmetaheuristicsandpatternformation.WhenI watched many BBC natural world programmes, I have always been trying to look for in- spiration from nature to design new metaheuristic algorithms. Over the last few years, I had managedto realize such dreamsby developingbatalgorithm,cuckoo search,andfireflyalgorithms,whichstarttoattractattentioninthecommunitiesof optimization, computational intelligence and engineering. Without Turing’s work on heuristics, it would almost be impossible to developthese new metaheuristics. Furthermore,looselyspeaking,artificialintelligencealsolargelyconcernsthecore algorithmstomimicintelligentbehaviour,unlessatrueTuringtestcanbepassedin the future,trulyintelligentalgorithmsmay still be a longway to go. However,on theotherhand,evolutionaryalgorithmsandmetaheuristicshavebecomeanimpor- tantpartofso-called‘smartalgorithms’andcomputationalintelligence.Theyhave started to permeate into many areas including artificial intelligence. Therefore, it isappropriatethatwecombineartificialintelligence,evolutionarycomputationand metaheuristicsinonebookanddedicatethisbooktoAlanTuring. During the peer-reviewprocess, many expertshave carriedout independentre- view of contributions. I would like to thank their help: Alma Garcia-Almanza, Ravindra Babu Tallamraju, Tamiru Alemu, Elena Benderskaya, Dalila Boughaci, Meftah Boudjelal, Larry Bull, Susmita Bandyopadhyay,Erik Cuevas, Amy Ding, Yue Deng, Janice Glasgow, Loreto Gonzalez-Hernandez,Yacine Laalaoui, Keyur Rana, Felipe Trujillo-Romero, Ricardo Sousa, Flvio Vieira, Abderrahmane Nitaj, Shahid Qamar, Vasyl Ustimenko, and Roman Yampolskiy. Special thanks to Ri- cardoSousaandVasylUstimenkowhohelpedmostinthereviewprocess. Iwouldliketothankoureditors,DrsThomasDitzingerandHolgerSchaepe,and staff at Springerfor their help and professionalism.Last but notleast, I thank my familyforthehelpandsupport. Xin-SheYang,2012 Contents PartI:Artificial Intelligenceand Cryptography TuringTestasaDefiningFeatureofAI-Completeness................ 3 RomanV.Yampolskiy ArtificialIntelligenceEvolvedfromRandomBehaviour:Departure fromtheStateoftheArt ........................................ 19 WiesławPietruszkiewicz,AkiraImada Turing:Then,NowandStillKey.................................. 43 KieranGreer ImitationProgrammingUnorganisedMachines ..................... 63 LarryBull TowardsMachineEquivalentConsciousness........................ 83 AmyWenxuanDing Multicriteria Models for Learning Ordinal Data: A Literature Review ....................................................... 109 Ricardo Sousa, Iryna Yevseyeva, Joaquim F. Pinto da Costa, JaimeS.Cardoso DiophantineandLatticeCryptanalysisoftheRSACryptosystem ...... 139 AbderrahmaneNitaj ArtificialIntelligenceMethodsinEarlyChildhoodEducation ......... 169 JimPrentzas Recursively Generated Evolutionary Turing Machines and EvolutionaryAutomata ......................................... 201 MarkBurgin,EugeneEberbach X Contents OnDynamicalSystemsofLargeGirthorCycleIndicatorandTheir ApplicationstoMultivariateCryptography......................... 231 VasylUstimenko,UrszulaRoman´czuk OnExtremalGraphTheory, ExplicitAlgebraicConstructionsof ExtremalGraphsandCorrespondingTuringEncryptionMachines .... 257 VasylUstimenko,UrszulaRoman´czuk AIMLKnowledgeBaseConstructionfromTextCorpora ............. 287 GiovanniDeGasperis,IsabellaChiari,NivaFlorio Multidisciplinary Trends in Modern Artificial Intelligence: Turing’sWay .................................................. 319 ElenaN.Benderskaya,SofyaV.Zhukova AnOverviewofComputationalSparseModelsandTheirApplications inArtificialIntelligence ......................................... 345 YueDeng,QionghaiDai,ZengkeZhang MiTSinDepth:AnAnalysisofDistinctTabuSearchConfigurations forConstructingMixedCoveringArrays .......................... 371 LoretoGonzalez-Hernandez,JoseTorres-Jimenez,NelsonRangel-Valdez PartII:Evolutionary Computationand Metaheuristics Metaheuristic Optimization: Nature-Inspired Algorithms and Applications................................................... 405 Xin-SheYang BatAlgorithmandCuckooSearch:ATutorial ...................... 421 Xin-SheYang MemoryandLearninginMetaheuristics........................... 435 ArifArin,GhaithRabadi On Some Aspects of Nature-Based Algorithms to Solve Multi-ObjectiveProblems ....................................... 477 SusmitaBandyopadhyay,RanjanBhattacharya ImageProcessingwithSpikingNeuronNetworks.................... 525 BoudjelalMeftah,OlivierLe´zoray,SoniChaturvedi,AleefiaA.Khurshid, AbdelkaderBenyettou CircleDetectiononImagesUsingLearningAutomata................ 545 ErikCuevas,FernandoWario,DanielZaldivar,MarcoPe´rez-Cisneros DecisionIncorporationin Meta-heuristicsto CopewithDecision SchedulingProblems ........................................... 571 YacineLaalaoui,R.B.Ahmad Contents XI EvolutionaryModelsforAgent-BasedComplexBehaviorModeling .... 601 ZengchangQin,YingsaiDong,TaoWan BankruptcyPredictionforBanks:AnArtificialIntelligenceApproach toImproveUnderstandability .................................... 633 Alma Lilia Garcia-Almanza, Biliana Alexandrova-Kabadjova, SerafinMartinez-Jaramillo NeuralNetworkBasedApproachesforNetworkTrafficPrediction..... 657 Fla´vio Henrique Teles Vieira, Victor Hugo Teles Costa, BrunoHenriquePereiraGonc¸alves ApplicationofBatAlgorithmandFuzzySystemstoModelExergy ChangesinaGasTurbine ....................................... 685 A.L.Tamiru,F.M.Hashim AKBRLInferenceMetaheuristicwithApplications ................. 721 LaurentiuBucur,AdinaFlorea,CatalinChera Multi-objectiveSimulatedAnnealingAlgorithmforPartnerSelection inVirtualEnterprises........................................... 751 HishamM.Abdelsalam,AmanyM.Mohamed MetaheuristicApproachesfortheWinnerDeterminationProblemin CombinatorialAuction.......................................... 775 DalilaBoughaci AuthorIndex ..................................................... 793 List of Contributors Editor: Xin-SheYang MathematicsandScientificComputing,NationalPhysicalLaboratory,Teddington TW110LW,UK E-mail:[email protected] Contributors: HishamM.Abdelsalam OperationsResearchandDecisionSupportDepartment,FacultyofComputersand Information,CairoUniversity,Cairo,Egypt E-mail:[email protected] BilianaAlexandrova-Kabadjova Av.5deMayoNo.1,Col.Centro,BancodeMe´xico,Mexico E-mail:[email protected] ArifArin Old Dominion University, Dept. of Engineering Management & Systems Engineering,241KaufmanHall,Norfolk,VA23529,USA E-mail:[email protected] R.BadlishahAhmad ComputerandCommunicationSchool,UniMAP,Kangar,Perlis,Malaysia SusmitaBandyopadhyay DepartmentofProductionEngineering,JadavpurUniversity,RajaS.C.Mallick Road,Kolkata,WestBengal,700032India E-mail:[email protected]