計(jì)算機(jī)程序設(shè)計(jì)論文范文

前言：我們精心挑選了數(shù)篇優(yōu)質(zhì)計(jì)算機(jī)程序設(shè)計(jì)論文文章，供您閱讀參考。期待這些文章能為您帶來啟發(fā)，助您在寫作的道路上更上一層樓。

第1篇

1計(jì)算思維的概述

何謂計(jì)算思維，即借助于計(jì)算機(jī)科學(xué)基礎(chǔ)概念來分析問題、解決問題、系統(tǒng)設(shè)計(jì)以及理解人類的一種行為。如下圖靈獎(jiǎng)得主ButlerLampson的報(bào)告，這種思維為人自身一種根本且概念化思維方式，是一種思想而非人造物，為數(shù)學(xué)與工程思維相互融合和互補(bǔ)所形成的一種思想。計(jì)算思維自身為抽象與自動(dòng)化，這種抽象是借助于嵌入、簡(jiǎn)化、遞歸以及轉(zhuǎn)換等方式，把某一個(gè)較為復(fù)雜的問題轉(zhuǎn)變成多個(gè)簡(jiǎn)單的子問題，并實(shí)施求解的一個(gè)過程。而自動(dòng)化則是指通過計(jì)算機(jī)自身所具運(yùn)算能力的充分利用來分析、解決各種問題，以此來彌補(bǔ)人在計(jì)算方面所存在的各種缺陷和不足，這種自動(dòng)化也在很大程度上使得計(jì)算機(jī)應(yīng)用范圍更為廣泛。基于上述這些內(nèi)容可知，計(jì)算思維其實(shí)就是一種人機(jī)共存、形式規(guī)整以及解答問題的思維。

2基于計(jì)算思維培養(yǎng)的C程序設(shè)計(jì)驗(yàn)教學(xué)

2.1教學(xué)目標(biāo)的明確

眾所周知，實(shí)施教育的主要目標(biāo)就在于學(xué)生綜合能力以及素質(zhì)的培養(yǎng)。目前我國教育部門在計(jì)算機(jī)教學(xué)目標(biāo)上予以了明確的規(guī)定，即計(jì)算機(jī)基礎(chǔ)教學(xué)能力培養(yǎng)的目標(biāo)應(yīng)包含四個(gè)方面的內(nèi)容，即計(jì)算機(jī)認(rèn)知能力、計(jì)算機(jī)應(yīng)用能力、網(wǎng)絡(luò)學(xué)習(xí)能力以及借助于計(jì)算機(jī)的一種共處能力，在這些目標(biāo)中，前兩個(gè)目標(biāo)所反映出來的內(nèi)容及就為計(jì)算環(huán)境以及問題求解。在計(jì)算機(jī)這門學(xué)科中，C程序的設(shè)計(jì)就是計(jì)算思維中的語言機(jī)問題求解。對(duì)此，在C程序設(shè)計(jì)教學(xué)過程中，計(jì)算思維這一能力不僅僅為其核心能力，同時(shí)也是教學(xué)中的核心內(nèi)容。鑒于上述內(nèi)容，在本次C程序設(shè)計(jì)實(shí)驗(yàn)教學(xué)上，教學(xué)目標(biāo)主要為計(jì)算機(jī)思維的培養(yǎng)，教學(xué)主要內(nèi)容為程序設(shè)計(jì)方式的講解，通過上機(jī)實(shí)踐的強(qiáng)化，使學(xué)生能夠借助于這種實(shí)踐感受，以及計(jì)算問題求解基本方式與思維模式的領(lǐng)悟，為學(xué)生創(chuàng)新能力的培養(yǎng)以及綜合素質(zhì)的提高打好基礎(chǔ)。下圖為C程序的設(shè)計(jì)的教學(xué)模塊。

2.2教學(xué)內(nèi)容的設(shè)計(jì)

在計(jì)算機(jī)這門學(xué)科中，C程序設(shè)計(jì)這一課程屬于理論和實(shí)踐并重的一門課程，要求教師在教學(xué)過程中，必須要把理論教學(xué)和實(shí)踐教學(xué)有機(jī)結(jié)合，從而使理論教學(xué)和實(shí)踐教學(xué)能夠互相推動(dòng)。在教學(xué)過程中，由于學(xué)生對(duì)于所學(xué)內(nèi)容缺乏一定的感性認(rèn)識(shí)，對(duì)此，教師在實(shí)施教學(xué)，應(yīng)綜合考慮學(xué)生自身的學(xué)習(xí)情況，結(jié)合所要學(xué)習(xí)的內(nèi)容，對(duì)C程序?qū)嶒?yàn)教學(xué)內(nèi)容進(jìn)行合理且科學(xué)地設(shè)計(jì)，把學(xué)生能力的培養(yǎng)、知識(shí)的傳授以及技能的訓(xùn)練等融為一體，使學(xué)生能夠在做的過程學(xué)到知識(shí)，在學(xué)習(xí)過程中獲得相應(yīng)的操作技能，繼而使其能夠?qū)⒆陨硭鶎W(xué)到的內(nèi)容與知識(shí)有效地應(yīng)用至實(shí)踐中，并解決在實(shí)踐中所遇到的各種問題。為達(dá)到理論夠用實(shí)踐突出這一目的，在本次C程序設(shè)計(jì)教學(xué)中，把所有的知識(shí)點(diǎn)歸納并總結(jié)為了九個(gè)核心點(diǎn)，根據(jù)所學(xué)內(nèi)容的難易程度，把教學(xué)過程細(xì)化成為三個(gè)模塊，即基礎(chǔ)能力、中級(jí)應(yīng)用以及高級(jí)應(yīng)用，基于由淺入深這一原則，循序漸進(jìn)地實(shí)施教學(xué)，把C程序?qū)嶒?yàn)教學(xué)分為了三個(gè)方面的實(shí)驗(yàn)，即驗(yàn)證實(shí)驗(yàn)、綜合實(shí)驗(yàn)以及設(shè)計(jì)型實(shí)驗(yàn)，通過這種方式，使學(xué)生能夠在記憶中來理解所學(xué)知識(shí)，并在理解中學(xué)會(huì)怎樣應(yīng)用這些知識(shí)，最后使學(xué)生在實(shí)踐應(yīng)用過程中學(xué)會(huì)創(chuàng)新。第一，通過驗(yàn)證型實(shí)驗(yàn)的實(shí)施，使學(xué)生能夠熟悉該語言的設(shè)計(jì)環(huán)境。學(xué)生實(shí)施編程以及應(yīng)用編程的一個(gè)基礎(chǔ)就是基礎(chǔ)能力模塊知識(shí)，在該模塊中，教師必須要求學(xué)生學(xué)會(huì)記憶以及理解，把該模塊實(shí)驗(yàn)教學(xué)內(nèi)容設(shè)置成為驗(yàn)證型的實(shí)驗(yàn)，讓學(xué)生對(duì)于C程序設(shè)計(jì)環(huán)境以及步驟有一個(gè)基本的認(rèn)識(shí)，使在學(xué)生熟悉這一環(huán)境后，了解該程序的書寫格式、特點(diǎn)以及結(jié)構(gòu)，了解并掌握該程序數(shù)據(jù)的基本類型、表達(dá)式以及運(yùn)算符等，繼而進(jìn)一步使學(xué)生掌握C程序數(shù)據(jù)的輸入以及輸出，明白C程序所具備的三種結(jié)構(gòu)，使學(xué)生通過驗(yàn)證型實(shí)驗(yàn)，可獨(dú)立解決編程方面存在的各種問題。在實(shí)施驗(yàn)證型實(shí)驗(yàn)教學(xué)時(shí)，應(yīng)要求學(xué)生應(yīng)按照教師解決問題的方式來完成相應(yīng)的實(shí)驗(yàn)內(nèi)容，這種模擬的方式就是計(jì)算思維的模仿，在這一環(huán)節(jié)中，所強(qiáng)調(diào)的是科學(xué)內(nèi)容活動(dòng)的演示以及證明，注重是學(xué)生實(shí)驗(yàn)操作、觀察、數(shù)據(jù)處理以及計(jì)算等個(gè)性化智力技能的培養(yǎng)，在教學(xué)過程中，學(xué)生借助于驗(yàn)證標(biāo)準(zhǔn)的這一已知程序來理解并學(xué)習(xí)基礎(chǔ)模塊中的內(nèi)容，在理解和學(xué)習(xí)的過程中，學(xué)生可直觀且清楚地看到在實(shí)際實(shí)驗(yàn)程序中各知識(shí)點(diǎn)的具體應(yīng)用，能夠更為快速地熟悉這種環(huán)境，繼而更為地理解以及記憶C程序設(shè)計(jì)的基本知識(shí)。此外，在學(xué)生實(shí)施驗(yàn)證型實(shí)驗(yàn)之前，教師應(yīng)實(shí)適時(shí)引導(dǎo)學(xué)生對(duì)以往所學(xué)C程序知識(shí)進(jìn)行回顧，并在基礎(chǔ)上對(duì)實(shí)驗(yàn)步驟實(shí)施討論，提出相關(guān)的注意事項(xiàng)，針對(duì)學(xué)生在實(shí)驗(yàn)中容易出錯(cuò)的這些操作方，教師應(yīng)該事先進(jìn)行示范，以免在實(shí)驗(yàn)中學(xué)生出現(xiàn)一些不必要的錯(cuò)誤。第二，通過設(shè)計(jì)型實(shí)驗(yàn)的實(shí)施，強(qiáng)化學(xué)生計(jì)算思維能力的培養(yǎng)。所謂設(shè)計(jì)型實(shí)驗(yàn)，就是指不同計(jì)算思維方式的綜合應(yīng)用來分析并解決各種問題。設(shè)計(jì)型實(shí)驗(yàn)是基于學(xué)生自身已掌握相應(yīng)的實(shí)驗(yàn)方法與技能，通過所學(xué)知識(shí)的應(yīng)用，自行提出相應(yīng)的問題，并在此基礎(chǔ)上分析和解決問題，經(jīng)過算法的分析、程序運(yùn)行結(jié)果的分析處理以及實(shí)驗(yàn)結(jié)果等，獲得正確且規(guī)范的研究分析理論。在這一環(huán)節(jié)中，所注重的是學(xué)生團(tuán)結(jié)協(xié)作、勇于探索以及的嚴(yán)謹(jǐn)求實(shí)精神的培養(yǎng)，在實(shí)施設(shè)計(jì)型實(shí)驗(yàn)教學(xué)時(shí)，教師應(yīng)事先對(duì)程序進(jìn)行填空、設(shè)計(jì)以及改錯(cuò)，并提出相關(guān)的思考問題，積極引導(dǎo)學(xué)生來討論與分析，鼓勵(lì)學(xué)生提出不同解決方案。第三，通過綜合型實(shí)驗(yàn)的實(shí)施，強(qiáng)化學(xué)生創(chuàng)新以及應(yīng)用意識(shí)的培養(yǎng)。在C程序設(shè)計(jì)實(shí)驗(yàn)教學(xué)中，為培養(yǎng)學(xué)生創(chuàng)新精神以及探索精神，使其計(jì)算思維得到擴(kuò)展與升華，可結(jié)合學(xué)生自身的學(xué)習(xí)進(jìn)度，基于所學(xué)內(nèi)容的難易程度，定期設(shè)計(jì)一個(gè)相應(yīng)的綜合型實(shí)驗(yàn)程序題目，鼓勵(lì)學(xué)生在課外課余時(shí)間來編程，同時(shí)在規(guī)定的時(shí)間內(nèi)把所自己的所編程的這一源程序上傳至電腦，由教師來進(jìn)行批閱，對(duì)于參與這一活動(dòng)的學(xué)生，教師應(yīng)該實(shí)施相應(yīng)的鼓勵(lì)，這樣不僅能夠進(jìn)一步激發(fā)學(xué)生學(xué)習(xí)的興趣，同時(shí)還可提供學(xué)生的實(shí)踐操作能力，使學(xué)生今后能夠更好地適應(yīng)社會(huì)市場(chǎng)，在潛移默化中使學(xué)生應(yīng)用創(chuàng)新能力以及計(jì)算思維得到培養(yǎng)。總之選擇了一些趣味性強(qiáng)、有吸引力的例子和話題以提高學(xué)生的學(xué)習(xí)興趣，選擇一些實(shí)用性強(qiáng)的例子和話題，以努力提高高校學(xué)生的工程實(shí)踐能力。精選的“不斷提升”的引導(dǎo)性例題、習(xí)題和實(shí)驗(yàn)題，以及貫穿全書的綜合實(shí)例，起到了開拓思路、引導(dǎo)讀者探究問題求解方法、激發(fā)讀者程序設(shè)計(jì)興趣的目的。

2.3基于計(jì)算思維能力培養(yǎng)的C程序設(shè)計(jì)實(shí)驗(yàn)教學(xué)

第一，上機(jī)操作實(shí)驗(yàn)流程的規(guī)范。在教學(xué)之前，教師應(yīng)該要求學(xué)生對(duì)所學(xué)內(nèi)容進(jìn)行預(yù)習(xí)，通過題目的分析，明確實(shí)驗(yàn)教學(xué)中所需的數(shù)據(jù)結(jié)構(gòu)，對(duì)參與運(yùn)算的這些變量進(jìn)行賦值，接著應(yīng)用三種結(jié)構(gòu)來解決問題，將結(jié)果輸出，進(jìn)行N-S流程圖的繪制，基于該圖編寫相應(yīng)的源程序，最后準(zhǔn)備好測(cè)試程序所需的數(shù)據(jù)以及預(yù)期結(jié)果，進(jìn)行上級(jí)調(diào)試工作，并歸納總結(jié)。通過實(shí)驗(yàn)流程的規(guī)范，不僅便于學(xué)生良好學(xué)習(xí)習(xí)慣以及思維習(xí)慣的培養(yǎng)，同時(shí)還可提升學(xué)生分析與解決各種問題的能力。

第二，加強(qiáng)上機(jī)操作過程中的指導(dǎo)與引導(dǎo)。在學(xué)生實(shí)際上機(jī)操作時(shí)，教師可借助于提問的方式來引導(dǎo)學(xué)生將自身所存在的問題找出來。在程序調(diào)試、上機(jī)輸入以及編輯時(shí)，除了系統(tǒng)所引發(fā)的問題外，通常情況下，其他問題均由學(xué)生自己來獨(dú)立解決。此外，在教學(xué)過程中，教師還還應(yīng)鼓勵(lì)學(xué)生采用不同的算法，正確引導(dǎo)學(xué)生反思這些算法，繼而培養(yǎng)學(xué)生的計(jì)算思維能力。現(xiàn)以“打印水仙花樹”以案例說明。

第三，加強(qiáng)實(shí)驗(yàn)過程的反思，采取合理且科學(xué)的考核評(píng)價(jià)制度，使學(xué)生的計(jì)算思維能夠得到擴(kuò)展。在上機(jī)完成以后，教師應(yīng)要求學(xué)生對(duì)于本次實(shí)驗(yàn)實(shí)施反思、總結(jié)以及歸納，可采取小組的方式來交流和溝通，集思廣益，使學(xué)生在交流和反思的過程中，拓展其計(jì)算思維。此外，還應(yīng)采取相應(yīng)的考核評(píng)價(jià)措施，可采取機(jī)考與筆試，結(jié)合學(xué)生平時(shí)學(xué)習(xí)表現(xiàn)情況，合理且科學(xué)地評(píng)價(jià)，對(duì)于學(xué)生所獲得的成功，不管大小，均應(yīng)予以相應(yīng)的肯定，以此激發(fā)學(xué)生學(xué)習(xí)的積極性。下面以“打印水仙花數(shù)”為例，簡(jiǎn)要說明基于計(jì)算思維的案例設(shè)計(jì)的基本方法。“打印水仙花數(shù)”案例設(shè)計(jì)步驟（圖3）打印水仙花數(shù)”案例的具體設(shè)計(jì)與實(shí)施（圖4）

3結(jié)束語

第2篇

西安理工大學(xué)工科非計(jì)算機(jī)專業(yè)和計(jì)算機(jī)專業(yè)雖然都開設(shè)C語言程序設(shè)計(jì)課程，但是前者具有鮮明的專業(yè)特點(diǎn)，對(duì)該課程的要求明顯不同，僅僅按照“面向?qū)ο蠼虒W(xué)”的原則，適當(dāng)調(diào)整教學(xué)組織活動(dòng)和教學(xué)內(nèi)容對(duì)于后者是遠(yuǎn)遠(yuǎn)不夠的。針對(duì)目前工科非計(jì)算機(jī)專業(yè)C語言程序設(shè)計(jì)課程教學(xué)實(shí)踐中所暴露的主要問題，筆者積極開展了非計(jì)算機(jī)專業(yè)C語言程序設(shè)計(jì)課程教學(xué)設(shè)計(jì)的教改工作。

1．1教學(xué)設(shè)計(jì)概述

所謂教學(xué)設(shè)計(jì)，就是為了達(dá)到一定的教學(xué)目的，對(duì)教什么(課程、教學(xué)內(nèi)容等)和怎么教(組織、方法、媒體的使用等)進(jìn)行設(shè)計(jì)。教學(xué)設(shè)計(jì)不等同于傳統(tǒng)的備課寫教案。教學(xué)設(shè)計(jì)有利于教學(xué)工作的科學(xué)化，使教學(xué)活動(dòng)納入科學(xué)的軌道。教學(xué)設(shè)計(jì)的意義就在于追求教學(xué)效果的最優(yōu)化，不僅關(guān)心教師如何教，更關(guān)心學(xué)生如何學(xué)，注重將人類對(duì)教與學(xué)的研究結(jié)果和理論綜合應(yīng)用于教學(xué)實(shí)踐。教學(xué)設(shè)計(jì)主要包括確定教學(xué)目標(biāo)、組織教學(xué)內(nèi)容、分析教學(xué)對(duì)象、選擇教學(xué)形式和方法及教學(xué)媒體、設(shè)計(jì)教學(xué)過程、教學(xué)質(zhì)量評(píng)價(jià)設(shè)計(jì)等基本環(huán)節(jié)，其中，設(shè)計(jì)教學(xué)過程是課程教學(xué)設(shè)計(jì)的核心。

1．2該課程教學(xué)設(shè)計(jì)的內(nèi)容

西安理工大學(xué)C語言程序設(shè)計(jì)課程組于2003年出版了《C語言程序設(shè)計(jì)教程》及配套的《C語言程序設(shè)計(jì)教程上機(jī)實(shí)驗(yàn)與學(xué)習(xí)指導(dǎo)》特色教材。自2011年開始，非計(jì)算機(jī)專業(yè)選用的教材與計(jì)算機(jī)專業(yè)不同。目前非計(jì)算機(jī)專業(yè)選用《C語言程序設(shè)計(jì)》(第1版，張毅坤教授，高等教育出版社，2011)作為該課程的教材。非計(jì)算機(jī)專業(yè)C語言程序設(shè)計(jì)的教學(xué)設(shè)計(jì)是一項(xiàng)復(fù)雜的系統(tǒng)工程，主要包括課程教學(xué)設(shè)計(jì)、章節(jié)教學(xué)設(shè)計(jì)、課堂教學(xué)設(shè)計(jì)和實(shí)驗(yàn)教學(xué)設(shè)計(jì)，以西安理工大學(xué)C語言程序設(shè)計(jì)課程教學(xué)大綱為指導(dǎo)，以《C語言程序設(shè)計(jì)》(第1版)及其配套教材為基礎(chǔ)，確定課程教學(xué)設(shè)計(jì)的內(nèi)容:①將該課程的教學(xué)目標(biāo)確定為“掌握C語言的基本語法和語義，理解結(jié)構(gòu)化程序設(shè)計(jì)的思想和方法，提高學(xué)生的編程能力和調(diào)試程序的能力”。②組織教學(xué)內(nèi)容的關(guān)鍵是進(jìn)行教材的組織呈現(xiàn)，理論教學(xué)內(nèi)容包括《C語言程序設(shè)計(jì)》(第1版)的第一章至第八章，實(shí)驗(yàn)教學(xué)體現(xiàn)于該教材的第九章及配套教材。③學(xué)生作為教學(xué)對(duì)象始終是教學(xué)過程中的重要角色，工科非計(jì)算機(jī)專業(yè)的種類多，分析教學(xué)對(duì)象就是掌握學(xué)生特點(diǎn)與了解專業(yè)背景并重。④重點(diǎn)突出課堂教學(xué)設(shè)計(jì)，傳統(tǒng)教學(xué)與案例教學(xué)有機(jī)結(jié)合，“講解+多媒體演示+課堂板書”缺一不可。⑤設(shè)計(jì)教學(xué)過程與“組織教學(xué)內(nèi)容”聯(lián)系最為緊密，主要包括課堂教學(xué)設(shè)計(jì)和實(shí)驗(yàn)教學(xué)設(shè)計(jì)，教學(xué)過程設(shè)計(jì)遵循的總原則是:激發(fā)學(xué)生興趣，注重能力培養(yǎng)，合理安排教學(xué)順序，講清重點(diǎn)與化解難點(diǎn)緊密結(jié)合，課堂提高與課后鞏固拓展有機(jī)統(tǒng)一，并預(yù)測(cè)教學(xué)實(shí)踐中可能出現(xiàn)的意外情況。⑥將學(xué)生評(píng)價(jià)、同行評(píng)價(jià)、教學(xué)督導(dǎo)組專家評(píng)價(jià)、主管教學(xué)的領(lǐng)導(dǎo)評(píng)價(jià)和教師自我評(píng)價(jià)這幾種評(píng)價(jià)的結(jié)果綜合起來，比較客觀的評(píng)價(jià)教學(xué)效果與教學(xué)質(zhì)量。

2教學(xué)設(shè)計(jì)的實(shí)踐及效果

我們連續(xù)多年承擔(dān)非計(jì)算機(jī)專業(yè)C語言程序設(shè)計(jì)課程，先后承擔(dān)過西安理工大學(xué)電氣工程及其自動(dòng)化(電力)、水文與水資源工程、印刷工程、包裝工程和材料科學(xué)與工程等專業(yè)的C語言程序設(shè)計(jì)的理論教學(xué)和實(shí)驗(yàn)教學(xué)任務(wù)。始終將上述教學(xué)設(shè)計(jì)的內(nèi)容貫穿于課堂教學(xué)和實(shí)驗(yàn)教學(xué)之中。C語言程序設(shè)計(jì)本身是一門實(shí)踐性很強(qiáng)的課程，加之各個(gè)理工科專業(yè)的特色鮮明，所以結(jié)合學(xué)生所學(xué)專業(yè)特點(diǎn)與需求，同一門課程，針對(duì)不同專業(yè)的學(xué)生，適當(dāng)調(diào)整教學(xué)設(shè)計(jì)內(nèi)容，并在教學(xué)實(shí)踐中檢驗(yàn)教學(xué)效果。2012年以來，學(xué)生對(duì)筆者的教學(xué)評(píng)分一直在95分以上，也給予了肯定性的評(píng)價(jià)，例如“采用啟發(fā)式教學(xué)，闡述問題深入淺出，重點(diǎn)突出，能理論聯(lián)系實(shí)際或聯(lián)系學(xué)科發(fā)展的新成果”;“對(duì)于您的授課方式我們很滿意，感謝您對(duì)這門課程的熱忱，我們會(huì)努力學(xué)下去”;等等。

3結(jié)語

第3篇

關(guān)鍵詞遺傳算法；TSP；交叉算子

1引言

遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。總的說來，遺傳算法是按不依賴于問題本身的方式去求解問題。它的目標(biāo)是搜索這個(gè)多維、高度非線性空間以找到具有最優(yōu)適應(yīng)值(即最小費(fèi)用的)的點(diǎn)[1]。

基本遺傳算法是一個(gè)迭代過程，它模仿生物在自然環(huán)境中的遺傳和進(jìn)化機(jī)理，反復(fù)將選擇算子、交叉算子和變異算子作用于種群，最終可得到問題的最優(yōu)解和近似最優(yōu)解。

2遺傳算法程序設(shè)計(jì)改進(jìn)比較

2.1基本遺傳算法對(duì)TSP問題解的影響

本文研究的遺傳算法及改進(jìn)算法的實(shí)現(xiàn)是以C++語言為基礎(chǔ)，在Windows2000的版本上運(yùn)行，其實(shí)現(xiàn)程序是在MicrosoftVisualStadio6.0上編寫及運(yùn)行調(diào)試的。

1)遺傳算法的執(zhí)行代碼

m_Tsp.Initpop()；//種群的初始化

for(inti=0；i<m_Tsp.ReturnPop()；i++)

m_Tsp.calculatefitness(i)；//計(jì)算各個(gè)個(gè)體的適應(yīng)值

m_Tsp.statistics()；//統(tǒng)計(jì)最優(yōu)個(gè)體

while(entropy>decen||variance>decvar)//m_Tsp.m_gen<100)

{

//將新種群更迭為舊種群，并進(jìn)行遺傳操作

m_Tsp.alternate()；//將新種群付給舊種群

m_Tsp.generation()；//對(duì)舊種群進(jìn)行遺傳操作，產(chǎn)生新種群

m_Tsp.m_gen++；

m_Tsp.statistics()；//對(duì)新產(chǎn)生的種群進(jìn)行統(tǒng)計(jì)

}

2)簡(jiǎn)單的遺傳算法與分支定界法對(duì)TSP問題求解結(jié)果的對(duì)比

遺傳算法在解決NPC問題的領(lǐng)域內(nèi)具有尋找最優(yōu)解的能力。但隨著城市個(gè)數(shù)的增加，已沒有精確解，無法確定遺傳算法求解的精度有多高。一般情況下，當(dāng)?shù)鷶?shù)增大時(shí)，解的精度可能高，但是時(shí)間開銷也會(huì)增大。因此可以通過改進(jìn)遺傳算法來提高搜索能力，提高解的精度。

2.2初始化時(shí)的啟發(fā)信息對(duì)TSP問題解的影響

1)初始化啟發(fā)信息

在上述實(shí)驗(yàn)算法的基礎(chǔ)上，對(duì)每一個(gè)初始化的個(gè)體的每五個(gè)相鄰城市用分支界定法尋找最優(yōu)子路徑，然后執(zhí)行遺傳算法。

2)遺傳算法與含有啟發(fā)信息的遺傳算法求解結(jié)果的對(duì)比

當(dāng)城市數(shù)增至20個(gè)時(shí)，用分支定界法已經(jīng)不可能在可以接受的時(shí)間內(nèi)得到精確的解了，只能通過近似算法獲得其可接受的解。試驗(yàn)設(shè)計(jì)中算法的截止條件：固定迭代1000代。表2中的平均最優(yōu)解為經(jīng)過多次試驗(yàn)(10次以上)得到的最優(yōu)解的平均值，最優(yōu)解的出現(xiàn)時(shí)間為最優(yōu)解出現(xiàn)的平均時(shí)間，交叉操作次數(shù)為最優(yōu)解出現(xiàn)時(shí)交叉次數(shù)的平均值。

表220個(gè)城市的TSP問題求解結(jié)果數(shù)據(jù)

算法交叉操作

次數(shù)最優(yōu)解

出現(xiàn)時(shí)間平均

最優(yōu)解

簡(jiǎn)單遺傳算法80244.479.4s1641.8

含初始化啟發(fā)信息的GA79000.237.4s1398.9

從表2中可以看出，當(dāng)初始種群時(shí)引入啟發(fā)信息將提高遺傳算法的尋優(yōu)能力。同時(shí)縮短了遺傳算法的尋優(yōu)時(shí)間和問題的求解精度。

2.3交叉算子對(duì)TSP問題解的影響

1)循環(huán)貪心交叉算子的核心代碼

for(i=1；i<m_Chrom；i++)

{

flag=0；

city=m_newpop[first].chrom[i-1]；//確定當(dāng)前城市

j=0；

while(flag==0&&j<4)

{

sign=adjcity[city][j]；//adjcity數(shù)組的數(shù)據(jù)為當(dāng)前城市按順序排列的鄰接城市

flag=judge(first，i，sign)；//判斷此鄰接城市是否已經(jīng)存在待形成的個(gè)體中

j++；

}

if(flag==0)//如果所有鄰接城市皆在待擴(kuò)展的個(gè)體中

{

while(flag==0)

{

sign=(int)rand()/(RAND_MAX/(m_Chrom-1))；//隨機(jī)選擇一城市

flag=judge(first，i，sign)；

}

}

if(flag==1)

m_newpop[first].chrom[i]=sign；

}

2)問題描述與結(jié)果比較

下面筆者用經(jīng)典的測(cè)試遺傳算法效率的OliverTSP問題來測(cè)試循環(huán)貪心交叉算子的解的精度和解效率。OliverTSP問題的30個(gè)城市位置坐標(biāo)如表3所示[2]。

從表4、圖1中可以看到，貪心交叉算子大大提高了遺傳算法的尋優(yōu)能力，同時(shí)也降低了交叉操作次數(shù)。在多次試驗(yàn)中，貪心交叉算子找到的最優(yōu)解與目前記載的最佳數(shù)據(jù)的誤差率為2.7%。而部分匹配交叉算子找到的最優(yōu)解與目前記載的最佳數(shù)據(jù)的誤差率高達(dá)7%。從而可以得到交叉算子對(duì)于遺傳算法

2.4并行遺傳算法消息傳遞實(shí)現(xiàn)的核心代碼

1)主程序代碼

//接收各個(gè)從程序的最優(yōu)個(gè)體

for(i=0；i<slave；i++)

{

MPI_Recv(Rchrom[i]，chrom，MPI_UNSIGNED，MPI_ANY_SOURCE，gen，MPI_COMM_WORLD，&status)；

}

//計(jì)算接收各個(gè)從程序的最優(yōu)個(gè)體的回路距離

for(i=0；i<slave；i++)

{

fitness[i]=0.0；

for(intj=0；j<chrom-1；j++)

fitness[i]=fitness[i]+distance[Rchrom[i][j]][Rchrom[i][j+1]]；

fitness[i]=fitness[i]+distance[Rchrom[i][0]][Rchrom[i][chrom-1]]；

}

//找到最優(yōu)的個(gè)體并把它記錄到文件里

for(i=0；i<slave；i++)

{

if(1/fitness[i]>min)

{

sign=i；

min=1/fitness[i]；

}

}

fwrite(&gen，sizeof(int)，1，out)；

for(i=0；i<chrom；i++)

fwrite(&Rchrom[sign][i]，sizeof(unsigned)，1，out)；

fwrite(&fitness[sign]，sizeof(double)，1，out)；

//每九代向從程序發(fā)送一個(gè)最優(yōu)個(gè)體

if(gen%9==0)

MPI_Bcast(Rchrom[sign]，chrom，MPI_UNSIGNED，0，MPI_COMM_WORLD)；

2)從程序代碼

//將上一代的最優(yōu)個(gè)體傳回主程序

MPI_Send(Rchrom1，chrom，MPI_UNSIGNED，0，gen，MPI_COMM_WORLD)；

//每九代接收一個(gè)最優(yōu)個(gè)體并將其加入種群中替換掉最差個(gè)體

if(gen%9==0)

{

PI_Bcast(Rchrom2，chrom，MPI_UNSIGNED，0，MPI_COMM_WORLD)；

Tsp.IndiAlternate(Rchrom2)；

}

//進(jìn)行下一代的計(jì)算

Tsp.Aternate()；

Tsp.Generation()；

Tsp.Statistics()；

3)并行遺傳算法的性能

筆者在MPI并行環(huán)境下，用C＋＋語言實(shí)現(xiàn)了一個(gè)解決TSP問題的粗粒度模型的并行遺傳算法。該程序采用的是主從式的MPI程序設(shè)計(jì)，通過從硬盤的文件中讀取數(shù)據(jù)來設(shè)置染色體長度、種群的規(guī)模、交叉概率和變異概率等參數(shù)。試驗(yàn)環(huán)境為曙光TC1700機(jī)，測(cè)試的對(duì)象是OliverTSP問題的30個(gè)城市的TSP問題。

正如在測(cè)試串行遺傳算法所提到的數(shù)據(jù)結(jié)果，并行遺傳算法也沒有達(dá)到目前所記錄的最好解，但是它提高了算法的收斂性，并行遺傳算法的收斂趨勢(shì)如圖2所示[4]。

圖2遺傳算法的收斂過程

3結(jié)束語

本文通過對(duì)基本遺傳算法的不斷改進(jìn)，證明了添加啟發(fā)信息、改進(jìn)遺傳算子和利用遺傳算法固有的并行性都可以提高遺傳算法的收斂性，其中對(duì)遺傳算法交叉算子的改進(jìn)可以大大提高遺傳算法的尋優(yōu)能力。

參考文獻(xiàn)

[1]劉勇、康立山，陳毓屏著．非數(shù)值并行算法－遺傳算法．北京：科學(xué)出版社1995.1

[2]IMOliverDJSmithandJRCHolland，Astudyofpermutationcrossoveroperatorsonthetravelingsalesman[C]//ProblemofthesecondInternationalConferenceonGeneticAlgorithmsandTheirApplication，Erlbaum1897：224-230