毕业设计（论文）外文翻译：数独问题的设计算法研究

本科毕业设计（论文）毕业设计（文献翻译）课题名称：数独问题的设计算法研究专业：信息与计算科学姓名：学号：指导教师：数理学院年月一，遗传算法（GAs）-实际注意事项1.随机的重要性GAs是一种随机算法，需要许多随机数，从上述示例可以看出，这有一些重要的意义。我们已经提到了其中的一个方面：使用具有置换的纯随机抽样可能产生失真，并且提到了一些在模拟文献中使用的减少方差的方法：需要使用一个好的伪随机数生成器（PRNG），另一个重要的方面，尚未广泛宣传。罗斯[240]向GA列表摘要发送了一个信息，其中包含了依靠提供标准软件PRNG的有益经验。然而，Meysenberg和Foster[165]进行了一些广泛的测试，由于不同的PRNG，对GA性能系统没有任何的影响，所以罗斯引用的案例可能是一个孤立的例子。尽管如此，最好的建议是使用经过彻底测试过的PRNG，如“数字食谱”[191]中所述的那些。2.约束优化到目前为止，我们已经忽视了对问题决策变量的限制问题，认为唯一的限制条件是单个变量的“框”约束，如2.2节0.4。然而，在许多情况下，表型变量的允许值可能会有相当复杂的限制。本质是：至少有一个保证（至少有简单的操作和编码），两个可行的父母解决方案将提供可行的后代。一些问题中，甚至可能难以找到合理多样化的初始种群的可行解决方案。一个普遍的策略是通过添加惩罚条件来修改适应度函数。Goldberg[96]给出的方法是这样的。但更广泛的经验表明，这不是最好的方法。我们简要讨论下面的一些替代方案，关于这个问题的更详细的考虑可以在Michalewicz和Schoenauer[167]的论文中找到。处罚限制问题最明显的解决办法就是忽略它们。如果遇到不可行的解决方案，则不允许进入人口（即“死刑”）。我们通常在约束边界上或附近找到全局最优值，使得稍微不可行的解可能相当接近最优解。因此，下一步是通过引入惩罚来修改目标函数。在这种情况下，理论上考虑允许适当的选择惩罚，这种情况很好，但是天真的使用惩罚的尝试通常会失败。如果惩罚太小，许多不可行的解决方案会被允许传播；如果它太大，搜索会仅限于搜索空间的内部，远离可行区域的边界。使用可变惩罚可能会有帮助[167]。修理受限问题的另一个解决方案是接受一个不可行的解决方案，在将其插入人口之前进行修复。这种做法常常要求一些生物学理由，不可行解决方案被视为不成熟的个体，尽管最初证明不适合其目标，但随着时间的推移，它们仍然可以发展成完全合理的解决方案。这种比喻也被应用于使用GA后代作为本地搜索的跳板的方法。（这样的混合动力被赋予了更为正式的规范，以Radcliffe和Surry[197]的模拟算法为名。）在这种情况下，还有一个确定是否应该是下一代应该使用的原始后代或修复版本的实际问题。修复后代意味着对搜索空间有希望的部分进行探索。戴维斯和他的同事[48,184]报道了一些实验数据，这表明，关于插入哪一个的决定应该是随机的，其插入修复版本的概率相当小。还有一个很好的例子，混合方法，原始的不可行解决方案进入人口，但它被给予修复版本的适应度。下一节将会对这个想法做更多的说明。多个目标许多作者建议使用不可行性作为次要目标，从而避免引入惩罚。Chu和Beasley最近的工作[38]在集合分区的上下文中提供了一个很好的例子。除了通常的适应度测量（基于真实的目标函数）之外，它们还定义了一个二次测量，它们称之为不适应，以表示给定解决方案中存在的不可行程度。生殖选择方案有利于最大限度地兼容字符串，而删除的选择是通过试图找到由新的后代所主导的现有的人口成员进行的。从某种意义上说，它的适应度更大，但不适合性不会更差，否则它的适应度不会更差，而其不适宜程度较低。多边目标GAs（MOGA）及其应用已由Fonseca和Fleming[84]进行了彻底的审查。修改运算符减轻标准运营商遇到困难的一种方法是设计适合该问题的运营商。TSP的边缘重组算子[304]（2.3.5节）就是典型的例子。改性制剂在某些情况下已经证明有成果的另一种方法是修改问题制定。Reeves[219]通过重新解决问题找到了解决包装问题的好方法。而不是使用子集选择解释，bin打包被视为排序问题，序列通过使用在线启发式解码。这种类型的问题的重新配置也已经用于其他应用程序.Chaffer和Eshelman[描述了在生产印刷电路板时极其复杂的线路平衡问题的类似方法。GA用于找到一个很好的序列，以提供一组产生最终解决方案的启发式方法。3.杂交通过与其他启发式的杂交可以总是提高GA的有效性。虽然使用GA的主要好处之一是自己的域名具有独立性，但这也是GAs执行效率低下的常见原因。引入特定问题可以大大提高解决方案的质量。杂交可以以各种方式进行。将种群（如上所述）与另一个特定问题的启发式结果相结合的想法可以被看作是一种杂交，但是最常见的方法是将其他启发式如邻域搜索或模拟退火整合到正常GA循环。有几个不同的选择，但一个典型的想法是应用一些标准突变和交叉算子来产生后代，然后在插入下一代之前，使用NS进行进一步修改。有多少人经历了这样的改善，无论NS阶段是否达到局部最佳状态，无论是最快上升还是使用更快的上升速度，人口多样性如何保持在激烈的收敛压力之下，这些都是必须的问题如何在任何特定的实现中得到解决。数字参与：推动学生成功1.离散程序设计与管理早期的研究强调了学生在减员中的作用，已经影响到提高学生成功的战术方法。在2004年和2010年的ACT报告“学生在保留中有什么作用？”调查受访者在被要求确定学生就业的根本原因时，绝大多数将学生因素与制度因素进行了比较。机构同意，学生因素如无准备，低收入，第一代身份，社会融合程度低等，对学生的消费起着至关重要的作用。机构制定了有针对性的方案，以便根据这些因素解决减员问题。Habley等人确定了90多个方案和实践，用于解决学生留学问题，包括新生研讨会，生活学习社区，金融知识课程，辅导，特殊人群咨询，补充教学，亚人计划，学习实验室和宿舍大厅计划。这些干预措施的所有权和管理权力下放，学生在学术部门接受辅导或辅导;有经济困难的学生被提到资金管理课程的经济援助;低收入/第一代学生可能被称为校园TRiO计划，等等。据FrankShushok和EileenHulme介绍，今天留学生保留的大部分理论已经从20世纪70年代开发的心理模式演变而来，这些心理模型涉及生活/工作应对问题。除了对参与进行研究外，教育工作者继续“关注病理学-重点是修复学生问题，珩磨学生为何离开，而不是为什么留学”。2.有限保留协调与沟通在权力下放的环境中，由于缺乏协调和沟通解决保留问题的方法的计划，劳动力的分散更频繁。尽管大学和大学企图组织自己来支持留学生，但需要更多的投资和承诺。大学董事会支持的全国学生保留实践研究表明，即使有人认为有人协调保留，实际上很少有时间去做这些努力。在这项研究中，75％的受访者报告说，他们的机构有责任负责协调工作和保留信息。当被问及这个人的职位的百分比正式承担这些职责时，大多数机构的报告为零。其他机构报告说，这个人的一些时间是致力于这些努力，全部范围从百分之一到百分之百，平均为百分之三十五。据高等教育咨询公司Noel-Levitz介绍，四年制公共和私人机构的三分之一尽管报告说已经实施了许多接受的保留计划，但并没有努力在教职员工和管理人员之间建立保留协议。在同一研究中，近一半的社区学院的受访者描述了他们的机构努力建立理解和保留问题的协议最低效。3.普及数据仓库沟通不仅不能跨越组织和功能界限，而且重要的信息也是孤立的。通过咨询，辅导，早期警报和部门计划所产生的数据仍然被困在组织和数据库中。学生信息系统（SIS）收集和存储数据，包括学生入学特征，课程模式和成绩，同时学习管理系统（LMS）收集和存储学生在线行为，登录频率，测验和任务等级的信息，以及对课程讨论委员会的贡献。程序管理员使用桌面数据库来获取在他们的计划中获得支持的学生的信息，特别是资助计划。辅导应用程序和在线教练服务捕获数据。咨询部门通过在SIS或咨询系统中创建的咨询相关屏幕获得技术支持。存在各种干预措施，从在线调查到旨在以早期警报能力服务的综合系统。所有这些数据被困在不同的数据存储中，对该机构具有微不足道的作用-它不能帮助机构支持和吸引学生。4.分裂方法引导这种分裂方法的后果如下。有限的牵引学生成果。高等教育不能要求学生坚持取得重大进步：根据国家学生资料交换所，2012年秋季开始在任何机构部门开办大学的所有学生中，68.7％在2013年秋季返回美国任何机构的大学，回报率为58.2％。2009年至2012年秋季队伍的保留率下降了全职队员的1.4％，首次兼职人员的0.3％。保留率的下降也影响到社区学院，同期的保留率首次下降了2.2％，全日制人口和首次兼职人数下降了1.0％。学生成绩的改善并不意味着学生的成功，干预对学生来说缺乏实用或有益。相反，它表明机构必须将他们的注意力从响应学生属性（即经典的风险指标）转移到他们的政策和结构如何影响学生的成功。此外，机构必须建立“预期相互关联的学习支持网络，预警系统和安全网”。学生成功的不完整画面对于与学生直接合作的学生，如学术顾问和计划人员，这种分散的方法使得以全面和有效的方式观看学生很难（不是不可能）。必须鼓励学生与校园活动和组织中的同龄人进行接触，并对促进学习和改进成果的教育行为进行投入。为了向学生提供有意义的鼓励，教师和专业顾问必须在整个机构的范围内快速查看学生信息。这意味着不仅要确定学生在哪里遇到困难，还要确定他或她正在改进，参与和卓越。分散方法的局限性超出了看到个别学生的完整画面。行政决策者必须看到学生人数在其机构中取得成功的广泛情况。了解学生遇到的常见困难是一个重要的难题，但同样重要的是，该机构必须更多地了解学生为什么留下来。为了在学生成功方面取得有意义的进展，机构必须“将学生成果进行语境化，并仔细研究制度政策和实践在学生保留中的作用”。这在数据孤岛，协调和沟通流程不佳的分散环境中很难做到。英翻汉（康宁）一、GeneticAlgorithms(GAs)-PracticalConsiderations1.TheimportanceofbeingrandomGAsarehighlystochasticalgorithms,needingmanyrandomnumbers,ascanbeseenfromtheaboveexample,andthishassomeimportantimplications.Oneaspectofthishasalreadybeenmentionedseveraltimes—thedistortionthatcanarisefromusingpurerandomsamplingwithreplacement,andsomemethodsofvariancereductionasusedinthesimulationliteraturehavebeenmentioned.Anotherimportantaspect,butonenotwidelypublicized,istheneedtouseagoodpseudo-randomnumbergenerator(PRNG).Ross[240]postedamessagetotheGAListDigestthatcontainedasalutarylessontothosewhorelyonthePRNGsprovidedwithstandardsoftware.However,MeysenbergandFoster[165]conductedsomeextensiveteststhatfailedtoshowanysystematiceffectonGAperformanceduetodifferentPRNGs,sothecasecitedbyRossmaybeanisolatedinstance.Nonetheless,itisbesttobeprepared,andthebestadviceistouseaPRNGthathasbeenthoroughlytested,suchasthosedescribedintheNumericalRecipesbooks[191].2.ConstrainedoptimizationSofarwehaveignoredthequestionofconstraintsonthedecisionvariablesofourproblem,orimplicitlyassumedthattheonlyconstraintsthatmatterare‘box’constraintsonindividualvariables,whichwemaymakeuseofinchoosingourrepresentation,asinSection2.2.4.However,inmanycasestheremaybequitecomplicatedsetsofconstraintsonthepermissiblevaluesofthephenotypicvariables.Theessenceofthedifficultyisclear:thereisrarelyaguarantee(atleastwithsimpleoperatorsandcodings)thattwofeasibleparentsolutionswillprovidefeasibleoffspring.Insomeproblemsitmayevenbedifficulttofindareasonablydiverseinitialpopulationoffeasiblesolutions.Apopularstrategyistomodifythefitnessfunctionbyaddingpenaltyterms.Goldberg[96]givestheimpressionthatthisisasimplematter,anditisoftenworthtryingit,butmoreextensiveexperiencehassuggestedthatthisisseldomthebestapproach.Webrieflydiscusssomeofthealternativesbelow,butafarmoredetailedconsiderationofthisquestionmaybefoundinthepaperbyMichalewiczandSchoenauer[167].PenaltiesThemostobvioussolutiontotheproblemofconstraintsissimplytoignorethem.Ifaninfeasiblesolutionisencountered,itisnotallowedtoenterthepopulation(i.e.,a‘deathpenalty’).Unfortunately,thisfailstorecognizethatthedegreeofinfeasibilitydoessupplysomeinformation.Itiscommontofindtheglobaloptimumonornearaconstraintboundary,sothatsolutionsthatareslightlyinfeasiblemayactuallybefairlyclosetotheoptimum.Thus,theobviousnextstepistomodifytheobjectivefunctionbyincorporatingpenalties.Therearecasesinwhichthisworkswell,wheretheoreticalconsiderationspermitanappropriatechoiceofpenalty,butanaiveattempttousepenaltiesoftenfails.Ifthepenaltyistoosmall,manyinfeasiblesolutionsareallowedtopropagate;ifitistoolarge,thesearchisconfinedtotheinteriorofthesearchspace,farfromtheboundariesofthefeasibleregion.Usingvariablepenaltiescanbehelpful[167].RepairAnotherpopularsolutiontoGAsforconstrainedproblemsistoacceptaninfeasiblesolution,buttorepairitbeforeinsertingitinthepopulation.Somebiologicaljustificationisoftenclaimedforthisapproach,alongthelinesthattheinfeasiblesolutionshouldbetreatedasanimmatureindividualthat,althoughinitiallydemonstrablyunfitforitspurpose,canneverthelessdevelopovertimeintoaperfectlyreasonablesolution.ThisanalogyhasalsobeenappliedtomethodsthatusetheGAoffspringasthespringboardforalocalsearch.(Suchhybridshavebeengivenamoreformalspecification.underthenameofmemeticalgorithmsbyRadcliffeandSurry[203].)Insuchcases,thereisalsothepracticalproblemofdecidingwhetheritshouldbetheoriginaloffspringortherepairedversionthatshouldbeusedinthenextgeneration.Insertingtherepairedoffspringmeanscurtailingtheexplorationofapromisingpartofthesearchspace.Davisandcolleagues[48,184]reportsomeinterestingexperimentalevidence,whichsuggeststhatthedecisionastowhichtoinsertshouldbeastochasticone,withafairlysmallprobabilityof5-10%ofinsertingtherepairedversion.Thereisalsoagoodcaseforamixtureofapproaches,wheretheoriginalinfeasiblesolutionentersthepopulation,butitisgiventherepairedversion’sfitness.MorewillbesaidaboutthisideabelowinthenextSection.MultipleobjectivesManyauthorshavesuggestedusinginfeasibilityasasecondaryobjective,thusavoidingtheintroductionofpenalties.RecentworkbyChuandBeasley[38]providesagoodexampleofthisideainthecontextofsetpartitioning.Inadditiontotheusualfitnessmeasure(basedonthetrueobjectivefunction),theydefineasecondarymeasurethattheycallunfitnesstorepresentthedegreeofinfeasibilitypresentinagivensolution.Theselectionschemeforreproductionfavouredstringsthatweremaximallycompatible,whileselectionfordeletionwascarriedoutbytryingtofindanexistingpopulationmemberthatwasdominatedbythenewoffspring—inthesenseeitherthatitsfitnessisgreaterwhileitsunfitnessisnoworse,orthatitsfitnessisnoworsewhileitsunfitnessisless.MultipleobjectiveGAs(MOGAs)andtheirapplicationhavethemselvesbeenthoroughlyreviewedbyFonsecaandFleming[84].ModifiedoperatorsOneapproachtoalleviatingthedifficultiesencounteredbythestandardoperatorsistodesignoperatorsthatareappropriatefortheproblem.Theedge-recombinationoperator[304]fortheTSP(Section2.3.5)isatypicalexample.ModifiedformulationAnotherapproachthathasprovedfruitfulinsomecasesistomodifytheproblemformulation.Reeves[219]foundgoodsolutionstobin-packingproblemsbyreformulatingtheproblem.Ratherthanusingthesubset-selectioninterpretation,binpackingwastreatedasasequencingproblem,withthesequencebeingdecodedbyusinganon-lineheuristic.Thistypeofproblemre-formulationhasalsobeenusedinotherapplications.SchafferandEshelman[255]describeasimilarapproachtoanextremelycomplicatedline-balancingproblemintheproductionofprintedcircuitboards.TheGAwasusedtofindagoodsequencetofeedtoasetofheuristicsthatproducedthefinalsolution.3.HybridizationTheeffectivenessofaGAcannearlyalwaysbeenhancedbyhybridizationwithotherheuristics.WhileoneofthemainbenefitsofusingaGAisoftenprofessedtobeitsdomainindependence,thisisalsoacommonreasonforGAsperformingineffectively.Introducingproblem-specificknowledgecanimprovesolutionqualityconsiderably.Hybridizationcanbecarriedoutinvariousways.Theideaofseedingapopulation(asdiscussedabove)withtheresultsofapplyinganotherproblem-specificheuristiccanbeviewedasatypeofhybridization,butthemostcommonapproachistointegrateotherheuristicssuchasneighbourhoodsearchorsimulatedannealingintothenormalGAcycle.Onceagainthereareseveraldifferentoptions,butatypicalideaistoapplysomestandardmutationandcrossoveroperatorstogenerateoffspring,whicharethenallowedtoundergofurthermodificationusingNSbeforebeinginsertedintothenextgeneration.Howmanyofthemundergosuchimprovement,whethertheNSphaseiscarriedontoalocaloptimum,whethersteepestascentorsomethingspeedierisused,howpopulationdiversityismaintainedinthefactoffierceconvergencepressure—theseareexamplesofquestionsthathavetobeaddressedinanyparticularimplementation.二、DigitalEngagement:DrivingStudentSuccess1.DiscreteProgramDesignandManagementEarlyresearchemphasizingthestudent'sroleinattritionhasinfluencedthetacticalapproachtoimprovestudentsuccess.Inboththe2004and2010ACTreports"WhatWorksinStudentRetention?"surveyrespondentsoverwhelminglyspecifiedstudentfactorsoverinstitutionalfactorswhenaskedtoidentifytheunderlyingcausesofstudentattrition.Institutionsagreedthatstudentfactorssuchasunpreparedness,lowincome,first-generationstatus,andpoorsocialintegrationplaythemostsignificantrolesinstudentattrition.Institutionshavedevelopedtargetedprogramstoaddressattritionbasedonthesefactors.Hableyetal.identifiedmorethan90programsandpracticesinusetoaddressstudentretentionissues,includingfreshmanseminars,living–learningcommunities,financialliteracyprograms,tutoring,advisingforspecialpopulations,supplementalinstruction,programsforsubpopulations,learninglabs,andresidencehallprograms.Theownershipandmanagementoftheseinterventionsaredecentralized,withstudentissueshandledbythedepartmentorunitthatseemsbestorganizedtoaddressaparticularissueordifficulty.Studentsreceivetutoringorsupplementalinstructionwithinacademicdepartments;studentswithfinancialproblemsarereferredtofinancialaidformoneymanagementclasses;low-income/first-generationstudentsmaybereferredtoacampusTRiOprogram,andsoforth.AccordingtoFrankShushokandEileenHulme,muchofthetheoryinstudentretentiontodayhasevolvedfrompsychologicalmodelsdevelopedinthe1970sthataddressedlife/workcopingproblems.Withtheexceptionofresearchonengagement,educatorscontinueto"keepaneyetowardpathology—focusingonrepairingstudentproblems;honinginonwhystudentsleaveratherthanwhystudentsstay."2LimitedCoordinationandCommunicationaboutRetentionIndecentralizedenvironmentsfragmentationofeffortoccursmorefrequentlyintheabsenceofaplantocoordinateandcommunicateaboutwaystoaddressretentionissues.Despiteattemptsbycollegesanduniversitiestoorganizethemselvestosupportstudentretention,moreinvestmentandcommitmentareneeded.AnationalstudyofstudentretentionpracticessupportedbytheCollegeBoardshowedthatevengivenaperceptionthat"someone"coordinatesretentionefforts,littletimeactuallygoestosuchefforts.Inthisstudy,75percentofrespondentsreportedthatsomeoneattheirinstitutionhadresponsibilityforcoordinatingeffortsandinformationaboutretention.Whenaskedwhatpercentageofthisperson'spositionwasformallycommittedtotheseduties,themajorityofinstitutionsreportedzeropercent.Otherinstitutionsreportedthatsomeofthisperson'stimewasdedicatedtotheseefforts,withthefullrangefromonepercentto100percent,withameanof35percent.AccordingtohighereducationconsultingcompanyNoel-Levitz,one-thirdoffour-yearpublicandprivateinstitutions,despitereportingthattheyhadimplementedmanyacceptedretentionprograms,werenotmakingeffortstobuildagreementamongfaculty,staff,andadministratorsaboutretentionandcompletionconcerns.Inthesamestudy,nearlyhalfofrespondentsatcommunitycollegesdescribedtheirinstitutions'effortstobuildunderstandingandagreementonretentionissuesasminimallyeffective.3PervasiveDataSilosNotonlydoescommunicationfailtocrossorganizationalandfunctionalboundaries,butvitalinformationremainsisolatedaswell.Datageneratedbyadvising,tutoring,early-alert,anddepartmentalprogramsstaystrappedwithinorganizationalanddatasilos.Studentinformationsystems(SISs)collectandstoredata,includingstudentadmissioncharacteristics,course-takingpatterns,andgrades,whilelearningmanagementsystems(LMSs)collectandstoreinformationonstudents'onlinebehaviors,loginfrequencies,quizandassignmentgrades,andcontributionstocoursediscussionboards.Programadministratorsusedesktopdatabasestocaptureinformationonstudentswhoreceivesupportintheirprograms,especiallygrant-fundedprograms.Tutoringapplicationsandonlinecoachingservicescapturedata.Advisingdepartmentsreceivetechnicalsupportthroughadvising-relatedscreenscreatedintheSISoradvisingsystems.Avarietyofinterventionsexist,fromonlinesurveystowell-integratedsystemsintendedtoserveinanearly-alertcapacity.Allofthisdata,whentrappedindisparatedatastores,hasmarginalusefulnesstotheinstitution—anditdoesnothelptheinstitutionsupportandengagestudents.4WhereFragmentedApproachesLeadTheconsequencesofthisfragmentedapproachfollow.LimitedTractiononStudentOutcomes.Highereducationcannotclaimsignificantgainsinstudentpersistenceandsuccess:AccordingtotheNationalStudentClearinghouse,ofallstudentswhostartedcollegeinanyinstitutionalsectorinfall2012,68.7percentreturnedtocollegeatanyU.S.institutioninfall2013,with58.2percentreturningtothesameinstitution.Retentionratesdeclinedbetweenthefallcohortsof2009and2012by1.4percentforfirst-time,full-timecohortsand0.3percentforfirst-time,part-timecohorts.Similardeclinesmarkedfull-andpart-timecohortsatprivateinstitutions.Decreasesinretentionalsoaffectedcommunitycolleges,whereretentionratesoverthesameperioddroppedby2.2percentforfirst-time,full-timecohortsand1.0percentforfirst-time,part-timecohorts.The