臺灣博碩士論文加值系統

在現今資訊科技發達的社會中，每個人家裡幾乎都有一部個人電腦，而在外出時也許會隨身攜帶著筆記型電腦或者拿來做為行動通訊的手機。在這些設備當中都有一個相同的特徵，就是有一個鍵盤當輸入資料的裝置，一般來說，鍵盤配置的好壞與否，就會影響到使用者的輸入文字的速度以及容易產生疲勞感的程度。所以到目前為止，已經有許多學者從事這方面的研究，然而並沒有人使用過粒子群演算法(Particle Swarm Optimization)來解決這樣的問題，並且在過去的研究中，大多以肢體健全的使用者角度來設計鍵盤，往往忽略了那些身心殘障的人，設計出來的鍵盤也許對前者使用上是非常好的，但是對於後者來說可能是難用不堪的。因此本研究利用粒子群演算法為基礎設計出一個可彈性依多準則條件的最佳化工具，讓使用者能夠根據自己本身的身體狀況，找出最理想的鍵盤配置。

Everyone almost has a personal computer at home in the developed science and technology of society. And someone also go out with a notebook or cell-phone. In these devices, they all have one same characteristic which has a keyboard as an inputting data device. It’s generally speaking that the better or not on the keyboard arrangement would have influences on typing speed of users and makes users feel tired easily. Up to now, there are many scholars engaged in such kind of research, but it still has no one using the particle swarm optimization algorithm to solve the keyboard arrangement problem. On the other hand, the past researches often had no thought for the disabled people. The new designed keyboard arrangement may be useful for the ordinary people but useless for the disabled people. Therefore, we design a flexible tool based on the particle swarm optimization algorithm in our research and users could use this tool to find the optimal keyboard arrangement according to their condition of bodies.

誌　謝 i
摘　要 ii
Abstract iii
目　錄 iv
圖　目　錄 vi
表　目　錄 vii
第一章　緒論 1
1.1　研究背景 1
1.2　研究目的 2
1.3　論文架構 4
第二章　文獻探討 5
2.1　鍵盤配置問題 5
2.1.1　標準鍵盤之文獻探討 5
2.1.2　多重符號鍵盤之文獻探討 7
2.2　粒子群演算法 10
第三章　研究方法 13
3.1　鍵盤配置問題定義 13
3.1.1　評估函數(Evaluation function) 14
3.1.2　智慧型預測輸入法 22
3.2　利用粒子群演算法解KAP 24
3.2.1　粒子的表現形式 24
3.2.2　適合度評估 25
3.2.3　粒子的位置更新 25
3.2.4　爬山理論 25
3.2.5　分支界定演算法 27
第四章　實驗結果 28
4.1　實驗環境 28
4.2　效能評估 28
4.2.1　3x3鍵盤 28
4.2.2　8x2鍵盤 33
4.2.3　資料庫 36
4.2.4　3x3鍵盤實驗結果 37
4.2.5　8x2鍵盤實驗結果 43
4.3　收斂分析 47
第五章　結論及未來展望 50
第六章　參考文獻 51

[1] J. Eggers, D. Feillet, S. Kehl, M.O. Wagner, and B. Yannou, “Optimization of the keyboard arrangement problem using an Ant Colony algorithm,”European Journal of Operational Research Volume: 148, Issue: 3, pp. 672-686, August 1 , 2003.
[2] P.S. Deshwal, and K. Deb, “Design of an Optimal Hindi Keyboard for Convenient and Efficient Use,” Technical Report KanGAL Report No. 2003005, Indian Institute of Technology, Kanpur, 2003.
[3] K. Sorensen,“Multi-objective optimization of mobile phone keymaps for typing messages using a word list,”European Journal of Operational Research, Volume: 179, Issue: 3, pp. 838-846, June 16, 2007.
[4] G.W. Lesher, B.J. Moulton, and D.J. Higginbotham,“Optimal Character Arrangements for Ambiguous Keyboards,”IEEE Transactions on Rehabilitation Engineering, 6, pp. 415-423, 1998.
[5] B.J. Oommen, R.S. Valiveti, and J.R. Zgierski,“An Adaptive Learning Solution to the Keyboard Optimization Problem,”IEEE Transactions on Systems, Man, Cybernetics, Volume: 21, No. 6, November/December, 1991.
[6] D.E. Goldberg,“Genetic Algorithms in Search, Optimization and Machine Learning.”Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA, 1989.
[7] S. Kirkpatrick, C. Gelatt Jr., and M. Vecchi,“Optimization by simulated annealing,”Science Volume: 220, No. 4598, pp. 671-680, 1983.
[8] F. Glover,“Tabu search–Part I,”ORSA Journal of Computing, pp. 190-206, 1989.
[9] M. Dorigo, “Optimization learning and natural algorithms,”Doctoral dissertation, Dip. Elettronica e Informazione, Politecnico di Milano, Italy, 1992.
[10] J. Kennedy, and R.C. Eberhart,“Particle swarm optimization,”Proceedings of the IEEE International Conference on Neural Networks, pp. 1942-1948, 1992.

[11] Zecevic, A., Miller, D., and Harburn, K.,“An evaluation of the ergonomics of three computer keyboards.”Ergonomics 43(1), pp. 55-72, 2000.
[12] Nevala-Puranen, N., Pakarinen, K., and Louhevaara, V., “Ergonomic intervention on neck, shoulder and arm symptoms of newspaper employees in work with visual display units,”International Journal of Industrial Ergonomics 31(1), pp. 1-10, 2003.
[13] R.C. Cassingham, “The Dvorak Keyboard:The Ergonomically Designed Typewriter, Now an American Standard,”Freelance Communications, Arcata, California, 1986.
[14] S.P. Ladany,“A model for optimal design of keyboards,”Computers & Operations Research 2(1), pp. 55-59, 1975.
[15] L.W. Light, and P.G.. Anderson, “Typewriter Keyboards via Simulated Annealing,”In AI Expert, September, 1993.
[16] K. De Jong,“Adaptive system design:a genetic approach,”IEEE Transactions on systems, Man, Cybernetics, pp. 566-574, 1980.
[17] S.H. Levine,“An adaptive approach to optimal keyboard design for nonvocal communication,”Proc.Int.Conf.Cybern. and Soc, pp. 334-337, 1985.
[18] S.H. Levine, S.L. Minneman, C.O. Getschow, and C. Goodenought-Trepagnier,“Computer disambiguation of multi-character text entry:An adaptive design approach,”Proc.IEEE Int. Conf.Syst., Man, Cybern., pp. 298-301, 1986.
[19] S.L. Minneman,“Keyboard optimization technique to improve the output rate of disabled individuals,”Proc. Ninth Annu. RESNA Conf., Minneapolis, MN, pp. 402-404, 1986.
[20] J.L. Arnott and M.Y. Javed, “Probabilistic character disambiguation for reduced keyboards using small text samples,”Augmentative and Alternative Communication, Volume: 8, pp. 215-223, 1992.
[21] S.H. Levine and C. Goodenough-Trepagnier, “Customised text entry devices for motor-impaired users,”Applied Ergonomics, Volume: 21, pp. 55-62, 1990.
[22] S.H Levine, C. Goodenough-Trepagnier, C.O. Getschow, and S.L. Minneman, “Multi-character key text entry using computer disambiguation,”in Proceedings of the 10th Annual Conference on Rehabilitation Engineering, Washington, DC: RESNA, pp. 177-179, 1987.
[23] R.A. Foulds, M. Soede, and H. van Balkom, “Statistical disambiguation of multi-character keys applied to reduce motor requirements for augmentative and alternative communication,”Augmentative and Alternative Communication, Volume: 3, pp. 192-195, 1987.
[24] Kumiko Tanaka-Ishii, Yusuke Inutsuka, and Masato Takeichi,“Entering Text with A Four-Button Device,”Proceedings of the 19th international conference on Computational linguistics, Volume: 1, pp. 1-7, 2002.
[25] Y.H. Shi, and R.C. Eberhart, “A modified particle swarm optimizer,”IEEE International Conference on Evolutionary Computation, Anchorage, Alaska, pp. 4-9, 1998.
[26] M. Clerc,“The swarm and the queen:towards a deterministic and adaptive particle swarm optimization,”Proc. Of 1999 Congress on Evolutionary Computation(CEC’99), Washington, DC, pp. 1951-1957, 1999.
[27] AOL T9® Text Input. Available from: http://www.t9.com
[28] Zi Corporation eZiText®. Available from: http://www.zicorp.com/eZiText.htm
[29] A. Lim, J. Lin, B. Rodrigues, and F. Xiao, “Ant colony optimization with hill climbing for the bandwidth minimization problem,”Applied Soft Computing, pp. 180-188, 2006.
[30] R. M’Hallah, “Minimizing total earliness and tardiness on a single machine using a hybrid heuristic,”Computers & Operations Research, pp. 3126-3142, 2007.
[31] A.M.A. Hariri,“A branch and bound algorithm for the two-stage assembly scheduling problem,”European Journal of Operational Research, pp. 547-556, 1997.
[32] M.-C. Portmann, A. Vignier, D. Dardilhac, and D. Dezalay,“Branch and bound crossed with GA to solve hybrid flowshops,”European Journal of Operational Research, pp. 389-400, 1998.