臺灣博碩士論文加值系統

無線廣播技術運用在生活中，讓收聽者可以很迅速找到其想要收聽的節目。本篇論文提出了一個應用基因演算法來解決在無線廣播中，將在無線廣播之中已經有的節目作一個編排，利用基因演算法的特性，將使用者選擇的節目，找到一組解是對於使用者比較好的解，且總接收的時間(total access time)為最短。

In mobile distributed systems the data on air can be accessed by a large number of clients. We define and analyze the problem of wireless data scheduling. We use a genetic algorithm (GA) to solve problem that wireless data scheduling. To search the best resolution, and total access time is the shortest. We also evaluate the performance of GA by experiments.

目　錄
書名頁 ………………………………………………………………… i
碩博士論文檔案上網授權書 ………………………………………… ii
論文指導教授推薦函 ………………………………………………… iii
論文口試委員審定書 ………………………………………………… iv
中文摘要 ……………………………………………………………… v
英文摘要 ……………………………………………………………… vi
誌謝 …………………………………………………………………… vii
目錄 ……………………………………………………………………viii
圖目錄 ………………………………………………………………… x
表目錄 ………………………………………………………………… xi
第一章 前言 ………………………………………………………… 1
第二章 無線環境與問題描述 ……………………………………… 7
第三章 基因演算法 ………………………………………………… 12
第一節 基因演算法與其他數值方法的比較 …………………… 13
第二節 基因演算法的基本結構 ………………………………… 15
第三節 基因演算法的流程圖 …………………………………… 16
第四節 基因演算法擁有的幾項優點 …………………………… 17
第五節 基因演算法搜尋程序的流程 …………………………… 18
第四章 我們的演算法 ……………………………………………… 19
第一節 編碼（Coding）………………………………………… 19
第二節 複製（Reproduction）………………………………… 20
第三節 交配（Crossover）……………………………………… 22
第四節 突變（Mutation）……………………………………… 24
第五節 適應性函數 ……………………………………………… 25
第六節 精英政策 ………………………………………………… 25
第七節 產生新一代的族群 ……………………………………… 25
第八節 流程圖 …………………………………………………… 26
第五章 實驗結果與討論 …………………………………………… 28
第六章 結論 ………………………………………………………… 37
第七章 參考文獻 …………………………………………………… 38
圖 目 錄
圖1 無線廣播的基本架構圖 ………………………………………… 1
圖2 無線廣播系統中的節目佇列 …………………………………… 9
圖3 基因演算法與其他數值方法 ………………………………… 13
圖4 基因演算法的基本結構 ……………………………………… 15
圖5 基因演算法的流程圖 ………………………………………… 16
圖6 無線廣播系統中節目的編碼方式 …………………………… 19
圖7 輪盤法 ………………………………………………………… 21
圖8 兩母體作交配演化的情形 …………………………………… 23
圖9 一個母體基因作突變的情形 ………………………………… 24
圖10 流程圖 ………………………………………………………… 26
圖11 改變選擇率，random與GA的TAT改變情形 …………………… 29
圖12 改變選擇率，TAT變化的情形 ………………………………… 30
圖13 400代~4000代，各代的變化情形……………………………… 32
圖14 改變頻道中的節目數目，TAT變化的情形 …………………… 31
圖15 改變讀者的數目，TAT變化的情形 …………………………… 35
表 目 錄
表1 符號定義 ……………………………………………… 2
表2 Random和GA改變選擇率所花費的時間 …………… 31
表3 Random和GA改變節目數目所花費的時間 ………… 34
表4 Random和GA改變讀者數目所花費的時間 ………… 36

【1】Kusung-dong, Yusung-gu, Taejon: QEM: A Scheduling Method for Wireless Broadcast Data. DASFAA 1999, pages 135-142.
【2】 S. Acharya, M. Franklin, and S. Zdonik. “Disseminating Updates on Broadcast Disks”. In Proceedings of Very Large Data Bases Conference, pages 354-365, 1996.
【3】 S. Acharya, R. Alonso, M. Franklin, and S. Zdonik. “Broadcast Disks : Data Management for Asymmetric Communication Enviroments”. In Proceedings of ACM SIGMOD Conference, pages 199-210, 1995.
【4】 S. Acharya, M. Franklin, and S. Zdonik. “Disseminating Updates on Broadcast Disks”. In Proceedings of Very Large Data Bases Conference, pages 354-365, 1996.
【5】 T. Imielinski, S. Viswanathan, and B. R. Badrinath. “Data on Air: Organization and Access”. Technical report, Rutgers University, 1994.
【6】 T. Imielinski, S. Viswanathan, and B. R. Badrinath. “Energy Efficient Indexing On Air”. In Proceedings of ACM SIGMOD Conference, pages 25-36, 1994.
【7】 C. Su, L. Tassiulas, and V. J. Tsotras. “Broadcast Scheduling for Information Distribution”. In Wireless Networks, 1998.
【8】 K. Tan and J. X. Yu. “Generating Broadcast Programs that Support Range Queries”. IEEE Transactions on Knowledge and Engineering,10(4), 1998.
【9】 Nobuo Funabiki and Yoshiyasu Takefuji. “A Paralle Algorithm for Broadcast Scheduling Problems in Packet Radio Networks”. IEEE Transactions on Communications, Vol. 41, No. 6, JUNE 1993.
【10】 Wolfgang Banzhaf. Peter Nordin. Robert E. Keller. Frank D. Francone. “Genetic Programming” Morgan Kaufmann Publishers, Inc. San Francisci, California, 1998.
【11】 David E. Goldberg. “Genetic Algorithms in search , optimization & machine learning”. Addison Wesley Longman, Inc, 1989.
【12】 Michael D. Vose. “The Simple Genetic Algorithm: Foundations and Theory”. Masschusetts Institute of Technology , 1999.
【13】Bryant A. Julstrom. “Very Greedy Crossover in a Genetic Algorithm for the Traveling Salesman Problem”. ACM, 1995.
【14】Ackley, David. “A connectionist Machine for Genetic Hillclimbing.” Kluwer Academic Publishers, Norwell, Massachusetts, 1987
【15】鍾雲恭、吳瑞煜, “使用基演算法求幾何規劃的最佳解”. The 2000 Conference on Technology and Management, pages 127-130