Zeki etmenlerde öğrenme kabiliyetinin geliştirilmesi ve dinamik bir atölye tipi çizelgeleme uygulaması

Abstract

Bilim ve teknolojideki hızlı gelişme, problemlerin gittikçe karmaşıklaşması araştırmacıları tüm disiplinlerde kullanılmak üzere yeni yaklaşımlara ve çözüm tekniklerine yöneltmiştir. Bilgisayarların hayata girmesi ile yeni metodlar için yeni imkanlar doğmuştur. Bunların başında kuşkusuz yapay zeka teknolojileri gelmektedir. İnsanın yaşamı boyunca kazandığı tecrübelerden ve bilinçsel eylemlerinden yararlanmak amacı ile gelişim gösteren yapay zekanın bu gün geldiği son noktalardan biri de zeki etmenlerin kullanımıdır. Zeki etmenler, çevrelerindeki olayları algılayabilen, birbirinden bağımsız hareket edebilen, bulundukları ortamlara uyum sağlayabilen otonom yazılım ve donanım birimleridir. Genel olarak algılama, kavrama ve eylem birimlerinden oluşurlar. Çevredeki olayları alıcılar yardımı ile algılayarak onları belirli amaçlar doğrultusunda yorumlarlar, efektörleri yardımı ile de çeşitli eylemleri gerçekleştirirler. Mesela bir zeki etmen bir robot ise, olayları algılayıp yorumladıktan sonra efektörlerine sağa, sola dönmesini, yürümesini, konuşmasını, bir vanayı açıp kapamasını vb gibi aktiviteleri yaptırabilir. Bunun yanında robotun yürüme eylemini gerçekleştirirken önüne çıkan engelleri farkedebilmesi, ezmemek üzere durması veya alternatif bir eylem gerçekleştirebilmesi de son derece önemlidir. Bu çerçevede zeki etmenlerin bir dış etki veya komut ile değil tamamen öz bilgileri ile her zaman aktif olarak eylemlerini yürütmeleri ve anlamlı bir algılamayı gerçekleştirdikleri an gerekli tepkiyi göstermeleri yazılım sistemlerine yeni imkanlar sağlamaktadır. [Becket ve Bedler. 1993].Zeki etmenler yazılım sistemlerine bir yapısal yenilik getirmiştir. Bundan yapay zeka ürünleri de payını almaktadır. Geleneksel sistemlerden farklı olarak sistem mimarilerini standardize ederek sanal ortamlarda canlılara benzer şekilde tamamen veya yarı özerk işlev yürütmeyi sağlamaktadır. Sistemlerin bundan böyle algılama- kavrama-eylem ana birimleri ile çatılarak hedeflenen görevleri yapmak üzere çevresi ile etkileşen bir zeki etmen haline dönüştürülmelerini önermektedir. Hedeflenen görevlerin karmaşıklığına göre bir sistemin birden fazla zeki etmen kullanılarak tasarlanmasını, zeki etmenlerin çevre ile ve kendi aralarında etkileşerek işlevleri yürütme imkanını getirmektedir. Bu yapısal yenilik sistemlerin her ortama kolaylıkla adapte edilebilmelerini sağlamaktadır. Zeki etmenlerin gerek bulundukları ortama rahat uyum sağlayabilmeleri gerekse yeni yetenekler kazanabilmeleri için eğitilebilmeleri oldukça önemli bir konudur. Zeki etmenlerin eğitilmesinde gerçek zamanlı öğrenmede yeterli bilginin her zaman sağlanamaması dolayısıyla doğal ortamlarda canlıların deneme-yanılma şeklinde öğrenmelerine benzer şekilde çoğunlukla destekli öğrenme stratejisinin kullanıldığı görülmektedir. Destekli öğrenme stratejisi ile geliştirilen algoritmalar çalışma şekli birbirlerine benzerler. En önemli benzerlik, hepsinin deneme-yanılma tekniğine göre öğrenme eylemini öngörmeleridir. Burada öğrenme, zeki etmenin çevreden algıladığı aktif duruma karşın bir davranış göstermesi ve bu davranışa çevreden veya bir destekçiden gelen uyarı ile durum-davranış arasında bir eşleştirme kurabilmesi şeklinde gerçekleşir. Bu olay şöyle gerçekleşir: Zeki etmen çevredeki bir durumu algılar, onu bir değerlendirme fonksiyonuna göre değerlendirerek, duruma karşılık yapması gereken davranışı belirler ve o davranışı uygular. Bu davranış çevrede bir durum değişmesine dolayısıyla yeni bir duruma neden olur. Öğrenme boyunca zeki etmenin davranışlarını izleyen bir destekleme mekanizması çevredeki bu değişikliği değerlendirerek etmene bir yönlendirme uyarısı gönderir. Bu yapılan davranışın uygun olup olmadığı konusunda zeki etmene bir fikir verir. Oluşan yeni durum ve alınan uyarı ile zeki etmen değerlendirme mekanizmasında kullandığı kriterleri güncelleştirir. Bu deneme-yanılma çevrimi zeki etmen ilgili durum-davranış ilişkisini kavrayıncaya kadar tekrarlanır. Bu işlemler esnasında bazı problemler ortaya çıkmaktadır. Bunlardan birincisi, geçici kredilendirme problemi olarak bilinen veöğrenme esnasında oluşan hatanın nasıl geriye doğru yayılması gerektiği konusudur. İkincisi ise, kazanılmış tecrübenin yeni durumlar için nasıl kullanılacağı konusudur. Bu da yapısal kredilendirme olarak bilinir. Bu her iki problemin çözümü için yapılmış çalışmalar farklı öğrenme algoritmalarının gelişmesini sağlamıştır. Destekli öğrenme algoritmaları olarak ortaya çıkan çalışamazların en eskilerinden birisi geçici farklar üzerine tasarlanmış olan AHC algoritmasıdır. Sutton (1988) tarafından geliştirilen bu algoritma bir çok uygulamaya konu olmuş ve yenilerinin geliştirilmesine de kaynak olmuştur. Bunun yanında Watkins (1989) tarafından geliştirilen Q-öğrenme algoritması da aynı şekilde yaygın bir uygulama alanı bulmuştur. Benzer şekilde, bir takım istatistiksel değerlemeye dayanan öğrenme algoritmaları ile genetik algoritmalara dayanan bir çok algoritma literatürde yerini almıştır. Bu çalışmada sağlam bir teorik tabanı ve pratik uygulama yelpazesi bulunan Q-öğrenme algoritması ve onun yukarıda ifade edilen geçici ve yapısal kredilendirme problemlerine çözüm getirecek iyileştirme önerileri sunulacaktır. Tez boyunca amaçlar Q-öğrenme algoritmasının hedeflenen problemleri irdelenmiştir. Bu irdeleme çerçevesinde üç kademeli bir iyileştirme gerçekleştirilmiştir. Birinci adımda yalnızca yerel optimum problemini çözmeye yönelik olarak O-l yordamı (cezalandırma fonksiyonu), ikinci adımda hem yerel optimuma hem de yavaş yakınsama problemine çözüm olmak üzere paralel güncelleştirme yaklaşımı (Q-II) önerilmiştir. Son adımda ise yerel optimum, yavaş yakınsama ve genelleştirme problemlerini çözen Q-III algoritması sunulmuştur. Bu gelişmelerden sonra yeni algoritma ile öğretilmek üzere tasarlanan zeki etmenin, dinamik iş çizelgeleme problemine yeni bir çözüm getirip getiremeyeceği araştırılmıştır. Yapılan çalışmalar sonunda zeki etmenlerin öğrenme kabiliyetlerini kullanarak dinamik atölye ortamında durumlara uygun iş çizelgelemeyi başarabildiği görülmüştür. Tezin ikinci bölümünde zeki etmenler genel olarak tanıtıldıktan sonra üçüncü bölümünde destekli öğrenme algoritmaları hakkında tanıtıcı bir literatür taraması verilmiştir. Bölüm 4'te dijit oyununu oynayacak bir zeki etmen tasarlanmış ve Q- XIIöğrenme algoritması ile eğitilme çalışması sunulmuştur. Bölüm 5 Q-öğrenme ile yapılan öğretim sırasında ortaya çıkan yerel optimum problemini aşmak amacı ile bir cezalandırma fonksiyonu içeren yeni bir Q-öğrenme (Q-I) tanıtılmıştır. Bölüm 6 ise Q-öğrenme` nin yavaşlığı problemi ele alınmış ve paralel güncelleştirme yaklaşımı ile yeni bir Q-öğrenme (Q-H) algoritması önerilmiştir. Bölüm 7 sunulan her iki yeni algoritma için bir yapısal kredilendirme sistemini, Bölüm 8 ise önerilen bu yapısal kredilendirme sistemini iyileştirmek amacı ile yeni bir Q-öğrenme algoritmasını (Q- 111) sunmaktadır. Bölüm 9'da Endüstri Mühendisliği'nin önemli problemlerinden olan atölyede iş çizelgeleme ele alınmıştır. Dinamik bir atölye ortamında iş çizelgelemesini tezgahlara iş atayarak yapacak olan bir zeki etmenin tasarlanması ve Q-I1I algoritması ile durumlara göre iş atamasının da hangi öncelik kuralını kullanacağını öğrenmesi ele alınmıştır. Bölüm 10'da da tezin sonuçları verilmiştir.

Intelligent agents are autonomous systems which perform appropriate behavior using their own knowledge in a dynamic environment. [Steels (1994), Wooldbridge and Jennings (1995), Hayes-Roth (1990), Brooks (1986), Maes and Brooks (1991), Dorigo and Colombetti (1994)]. They consist of three main parts: perception; to re ceive messages of environment, cognition; to evaluate these messages in order to make decisions, and action; to perform the decided action. The distinctive character istic of intelligent agents is their autonomous capability. Details on this topic are pre sented in Chapter 2. Learning, which can be defined as improving behavior through the time, is one of the most important topics in research on intelligent agents. In these agents, especially, reinforcement learning techniques are widely employed. In this case, the agent has to take a reinforcement signal which is produced against its actions into account. Among reinforcement learning algorithms, Q-learning is reported to be successfully implemented [Mahadevan and Connell (1992), Singh (1992), Lin (1992), and Barto etal(1995)]. Q-learning is realized as an asynchronous dynamic programming method which pro vides agents with the capability of learning to act optimally in Markovian domains by experiencing the consequences of actions, without requiring them to build map of the respective domain [Watkins and Dayan, (1992)]. The main idea behind the 0 learning is the use of a single data structure called the utility function (Q(x,a))- That is, the utility of doing action a in state x. During XIVlearning, this algorithm updates the value of Q(x,a) using <x,a,r,y> tuples, where r represents the reinforcement signal (payoff) of the environment and y represents the new state which is to be obtained after the execution of action a in state x. Q(x,a) is computed for each action as:- Q(x,a)= E(r + y e(y)/x,a). where y is a discounted constant value in [0,7] interval and e(y) is the expected value of;- this is also computed as:- e(y) - max/Q(y, a), for/fa/ Q-learning algorithm first initializes the Q value of each action to 0. It then repeats the following procedure. The action with the maximum Q value is selected and acti vated. Corresponding Q value of that action is then updated using the following equation (updating rule):- QT (x,a)*-Q' (x,a) + ^r + ye(y)-Q' (*,«)) where Q° (x.aj, Q11 (x,a) represent the old and the new Q values of action a in state x, and (3 is the learning coefficient changing in [0,7] interval. More information Q- learning algorithm can be found in details with a literature survey, in Chapter 3. An illustrative example is presented in Chapter 4 to show the problems which have been emerged during the implementation of Q learning. In this example, the agent deals with a set of vectors each which consists of 8 digits each. The aim of the agent is to transmit the initial state into the goal state through an iterative learning. In each iteration, the agent perceives a vector and tries to transmit it into the goal state using a set of behavioral rules (actions). The following rules are employed.. To make two digits as the same,. To make two digits as different,. To change one of the two digits. To change the places of the two digits (mutually). No change The agent has some limitations such as selecting and activating only one action at a time and considering at most randomly selected two digits in each action. The ran- xvdom selection of the digits makes the problem too difficult to handle. That is due to the fact that this problem has a non-Markovian nature. Since Q-learning is developed by using a Markovian decision process, it is not expected to be successful in this case. Therefore the algorithm needs to be modified in order to handle this. Q-learning algorithm works in such a way that the agent gains experience by trial and error throughout the execution of actions. During this process, the agent figures out how to assign credit or blame to each of its actions in order to improve the behavior. This is called temporal credit assignment. Once the agent learns how to behave, it can generalize the knowledge it posses and recall the knowledge when required. The ability of the agent to use its past experience (generalization) is called structural credit assignment. However, both, temporal credit assignment and generalization are not easy to achieve for certain problems such as the one described above. The problems suffered by traditional Q-learning procedure are discussed by White head and Lin (1995), traditional Q-learning was developed utilizing a Markovian decision process. Therefore, it may not be implemented as successful as expected for learning in non-Markovian domains. There may be two problems facing local opti mum and taking long time to learn. Some attempts have already been made to solve these problems. To overcome the local optimum problem, traditional Q-learning is modified and a punishment mechanism is employed in order to prevent the activation of the same action over and over again. This algorithm is called Q-l and its details are given in Öztemel and Aydın (1997). Although Q-l solves the local optimum problem in most of the cases, it takes too much time for the agent to reach the conclusion. In Chapter 5 and 6, two versions of Q-learning, called as Q-l and Q-II, are introduced to solve these problems. The main idea behind Q-l is to punish the consecutively performed behaviour which is selected in a wrong way. During the learning, a punishment mechanism observes the learning process to direct it into the right way. To perform the punishment, a function is constructed from Q values of non-selected behavior. Details are ex plained in Chapter 5. XVIQ-I managed to solve the local optima problem. However, the learning time remains as a problem. In order to solve both the local optimum and speed problem at the same time, Q-II learning algorithm is developed. As stated earlier, the local optimum is realized when the same action is activated more than a certain number of iteration. If not a local optimum, the agent usually takes too much time to learn how to select and execute the actions. The reason for this may be the activation of a single action at a time. It is believed that the execution of a single action may easily reveal the effect of that action within the environment [Lin, 1992]. Q-II propose to execute a single ac tion, but to update the utilization of all actions in parallel taking the fitness of the action into consideration. This prevents local optimum and enables learning more faster. Since all Q values are updated at each iteration, there is always a chance for an activity to be selected and executed. The performances of traditional Q, Q-I and Q-II are compared with respect to the local optimum and learning time for the problem defined in Chapter 6 Another stage of Q-learning studies is to concern with structural credit assignment (generalization) problem. Q-learning has not a generalization capability in nature. One of the aims of this thesis is to construct a robust structural credit assignment method which is considered in an off-line manner in Chapter 7 and with a new de velopment in Q-learning considered in an off-line manner in Chapter 8. The final version of Q-learning in this thesis is Q-III which composed of Q-II and Hard c- Means algorithms. To compose both algorithms, the expectation term, e(y), is rede fined as a distance function instead of a probabilistic maximum function. By these refinement, Q-learning composed with the clustering method to create a more defi nite structural generalization. Details are widely explained in Chapter 8. In Chapter 9, a dynamic job-shop scheduling system designed by intelligent agent technology is introduced. An intelligent agent is designed to schedule the jobs in the shop using three dispatching rules according to the jobs and shop floor states. Results are so satisfied that development of an intelligent agent based scheduling system in sophisticated manner can solve many problems of this area.