【文章內(nèi)容簡介】 cpf max1? (1) 式 (1)中 ， icmax 為覓食蜂 if 對應(yīng)調(diào)度的最大完工期 。 蜂群的平均收益率 colonypf 為 ? ?? nj jc olony pf 1 m a x11 (2) 式 (2)中 ， n 為 t 時刻搖尾舞的次數(shù) ； jcmax 為跳搖尾舞的覓食蜂 if 對應(yīng)調(diào)度的最大完工期 。 搖尾舞 持續(xù)時間 id 的計算公式為 ? ?colonyii pfpfd ? (3) (2) 覓食算法 覓食算法在蜂群中定義了一個覓食蜂群 ,這 些覓食蜂迭代地構(gòu)造出作業(yè)車間調(diào)度的解 。 覓食蜂在拓?fù)鋱D中沿著節(jié)點之間的邊行進 ， 一次性地訪遍圖中從起點到終點所有的節(jié)點 ， 由此得到的路徑即代表了可行解 。 覓食蜂只能基于工序的優(yōu)先權(quán)按照既定的可選節(jié)點清單選擇下一節(jié)點 ， 這樣的移動準(zhǔn)則表示為 ? ? ? ?? ? ? ?? ?? ? ? ??????可選節(jié)點j ijijijijij dtdttp??????11 (4) 式 (4)中 ， ijp 為路徑從節(jié)點 i 擴展至節(jié)點 j 的概率 ； ij? 為節(jié)點 i 和節(jié)點 j 之間連邊的等級數(shù) ； ijd 為 節(jié)點 i 和節(jié)點 j 之間的啟發(fā)式距離 。 節(jié)點 i 至節(jié)點 j 之間有向邊的等級數(shù) 9 ???????? mk mij ??? 1 (5) 式 (5)中 ， ? 為偏好 路徑 賦值 ， ?? ； k 為可選節(jié)點數(shù) ； m 為偏好路徑數(shù) ，1?m 或 0。 由于首次覓食的覓食蜂的 m 值等于 0， 則所有可選節(jié)點的 ij? 賦值相同 。 3 人工蜂群算 法的多線程并行實現(xiàn)技術(shù) 在如今的信息社會，計算機需要處理的信息量越來越龐大，需要解決的問題越來越復(fù)雜，使得計算量暴增 。 通過提高單個處理器的計算速度和采用傳統(tǒng)的“順序 (串行 )”計算技術(shù)已難以勝任 。 因此，需要功能更加強大的計算機系統(tǒng)和高效計算技術(shù)來支撐， 并行計算機 和并行計算技術(shù)由此應(yīng)運而生。加上第四代編程語言的出現(xiàn)，比如面向?qū)ο缶幊陶Z言 C++、 JAVA等都提供了多線程技術(shù)，不僅可以使編程者在單處理機上模擬并行計算，還可以在多處理機上實現(xiàn)并行計算 。 進程、 線程 與多線程 進程 、 線程 和多線程 都是 操作系統(tǒng)的概念 。 進程是程序在一個數(shù)據(jù)集合上運行的過程 ， 它是系統(tǒng)進行資源分配 和調(diào)度的一個獨立單位 ， 是應(yīng)用程序的執(zhí)行實例 。 進程在運行過程中創(chuàng)建的資源隨著進程的終止而被銷毀 ， 所使用的系統(tǒng)資源在進程終止時被釋放或關(guān)閉 ,即 具有動態(tài)性 ，從被創(chuàng) 建到被撤銷有一個生命周期 ； 是程序的一次執(zhí)行，即在指定內(nèi)存中的一組指令序列的執(zhí)行過程 。 每個進程由私有的虛擬地址空間、代碼、數(shù)據(jù)和其它各 種系統(tǒng)資源組成 。 一個進程至少包括一個線程 (稱為主線程 )，并且每個進程都由主線程開始 ， 在運行過程中可以建立新的執(zhí)行線程 。 線程是程序執(zhí)行的基本單位 ， 通過線程可以實現(xiàn)程序執(zhí)行的并發(fā)性、獨立性和異步性 。 每個線程都有自己的一套設(shè)備 (CPU、寄存器和堆棧 )，操作系統(tǒng)給每個獨立的線程安排一些 CPU時間片，通過操作系統(tǒng)的調(diào)度，實現(xiàn)不同線程的切換 。因此， 為了充分利用 CPU，引入了多線程 。 多線程是指程序中包含多個執(zhí)行流，即在一個程序中可以同時運行多個不同的線程來執(zhí)行不同的任務(wù)，也就是說允許單個程序創(chuàng)建多個并行執(zhí)行的線程來完成各自的任務(wù) 。 多線程是為了同步完成多項任務(wù)，不是為了提高運行效率，而是為了提高資源使用效率來提高系統(tǒng)的效率 。 線程是在同一時間需要完成 多項 任務(wù)的時候 實現(xiàn)的 。 多線程技術(shù)的主要優(yōu)勢在于充分利用 CPU的空閑時間片，用盡可能少的時間來對用戶的要求作出響應(yīng)，使系統(tǒng)整體運行效率得到一定的提高，增加 了 應(yīng)用程序的靈活性 。 10 多線程提高了系統(tǒng)響應(yīng)能力及平滑的后臺處理 。 例如，一個字處理程序 (進程 )可以通過使用多線程來加強操作并簡化與用戶的交互。該應(yīng)用程序可以包含 3 個線程，第 1 個線程可以用于響應(yīng)用戶的鍵盤輸入消息，將字符放入文檔中；第2 個線程可以執(zhí)行拼寫檢查及分頁等后臺操作 ； 第 3 個線程可以在后臺將文檔送到打印機打印 。 互斥鎖 臨界資源是指在系統(tǒng)中有很多資源是多個 進程共享的資源中一次僅允許一個進程使用的那部分資源 。 互斥 (間接相互制約關(guān)系 )指多個進程都想使用一個臨界資源 ， 但是不能 同時 使用，于是只好一個進程用完了，才能給其他 的 進程用 。 加鎖法是對臨界區(qū)加鎖以實現(xiàn)互斥 。 當(dāng)某個進程進入臨界區(qū)后 ， 就鎖定臨界區(qū)直到它退出臨界區(qū)，其他進程要進入時， 需 要不斷測試臨界區(qū)是否被用著，直到臨界區(qū)空著 時 才能進入 。 在編程中，引入了對象互斥鎖的概念，來保證共享數(shù)據(jù)操作的完整性 。 每個對象都對應(yīng)于一個可稱為 “ 互斥鎖 ” 的標(biāo)記，這個標(biāo)記用來保證在任一時刻，只能有一個線程訪問該對象 。 通常，互斥鎖通過確 保一次只有一個線程執(zhí)行代碼的臨界段來同步多個線程 。 信號量 信號量 S為可用 臨界資源 數(shù)量 ， 取值只允許為 “ 0” 和 “ 1” 的信號量稱為二元信號量，主要用作互斥變量 (mutex)；取值允許為整數(shù)的信號量稱為一般信號量 (semaphore)，主要用于進程間的同步問題 。 )(/)( ssignalswait 操作 ： 最初是由芬蘭學(xué)者 Dijkstra 于 1965年 提出的兩個原子操作概念 ， 信號量除初始化外僅能通過這兩個標(biāo)準(zhǔn)的原子操作 )(swait 和)(ssignal 來訪問。原子操作在執(zhí)行時 是 不可中斷的 ， 即當(dāng)一個 進 程在修改某信號量時 ， 沒有其他 進 程可同時對該信號量進行修改 ， 以解決進程間同步和互斥的問題。 )(swait 操作 ： 對某資源信號量 s 作 wait 操作 ， 表示申請資源 ， 可用資源數(shù) s ；如果 0?s ， 表示無資源可用 ， 本進程掛起 ， 變成等待資源 s 的“等待”狀態(tài) 。 )(ssignal 操作 ： 對某資源信號量 s 作 signal 操作 ， 表示釋放資源 ， 可用資源數(shù) 1??ss ； 如果 0?s ， 表示有進程在等待該資源 ， 則釋放該進程 ， 即將等待該資源 s 的首進程的狀態(tài)變?yōu)椤熬途w”狀態(tài) ， 去等待 CPU繼續(xù)運行 。 根據(jù)對互斥信號量 mutex的不同設(shè) 置方式 ， 基于信號量的生產(chǎn)者 消費者問題算法 [7]有兩種 ， (1) 生產(chǎn)者、消費者共 同使 用一個互斥信號量 mutex， 即生產(chǎn)者進程間、消費者進程間和生產(chǎn)者、消費者進程均互斥 ， 同一 時刻只 能有一個進程 11 訪問緩沖區(qū) ； (2)為生產(chǎn)者、消費者分別設(shè)置各自的互斥信號量，即生產(chǎn)者進程間使用 producerMutex進行互斥，消費者進程間使用 consumerMutex進行互斥，而生產(chǎn)者進程與消費者進程間不互斥 。 一旦有可用的資源，兩類進程就可以 同時訪問緩沖區(qū)，同一時刻最多允許兩個進程訪問緩沖區(qū)，由于本文的算法中，借鑒的是第二種算法的思想，所以此處只演示算法 (2)的流程圖 。 圖 5 生產(chǎn)者 消費者分別設(shè)置互斥量的流程圖 由于 算法 2中 同一 時刻 最多允許兩個進程訪問緩沖區(qū) ，所以 需要有兩個指針ptop 、 pbottom 來分別指向生產(chǎn)者、消費者的下一個寫入、讀取位置 。 4 基于人工蜂群算法的智力題求解 本文以“人工蜂群算法分析與實現(xiàn)”為題，在分析蜂群基本算法的基礎(chǔ)上，將其在智力題的求解中實現(xiàn)。 本文算法中 采用多個線程并行技術(shù)模擬多只蜜蜂在同一時刻各司其職， 完成各自的任務(wù)。 通過考慮所選智力題的特征和結(jié)合操作系統(tǒng)方面的相關(guān)知識 (諸如進程、線程、多線程、信號量、互斥鎖等 )提出數(shù)學(xué)模型，并在線程與線程之間添加一些限制條件來更好地模擬蜂群 ， 從而使多個智能性不高的線程也能像蜂群中不是很聰明的個體一樣，通過一定的信息交流、協(xié)作共同完成 智力題的求解 。 智力題求解問題概述 第一個答案是 b 的問題是哪一個？ 12 (a)2。 (b) 3。 (c)4。 (d)5。 (e)6