Endüstri Mühendisliği Yazıları-4 (Üretimde Genetik Algoritma)

Üretim planlama ve çizelgeleme tedarik zincirinin en zor problemlerindendir. Genel geçer bir yolu yoktur; çünkü her üretim tesisinin farklı beklenti ve kısıtları vardır. Bu kısıtların da genellikle küçük bir kısmı lineer, geriye kalanı ise non-lineerdir, kuadratiktir, başka bir şeydir, başa beladır. İşte bu yüzden kısa vadeli üretim planlama ve/veya çizelgeleme standart ERP çözümlerinde yer almaz. Ya kişiye özel çözüm üreten teknoloji firmaları devreye girip bunun için bir program yazar ya da insan aklıyla çözülür. İlki firmalara (genellikle) pahalı geldiği için ikincisi tercih edilir. Problemin matematiğe dökümü çok zor olduğu için bu işte üretim deneyimi olan birisi seçilir. Bu kişi problemin özünü (matematiksel olarak) tanımlayamasa da iyi bildiği için sorunu kafasında çözer. Sonra plan ya da çizelgesini yapıp üretimi yönlendirir. Genellikle de çok iyi iş çıkartırlar. Ama problem bazen onun da boyunu aşar ve çözmek için daha sofistike bir yol izlemek gerekir.

İşte, yıllar önce üretim planlamada çalışırken böyle bir problemle karşılaşmıştım. Çalıştığım şirketin üretim çizelgeleme işleri içinden çıkılmaz hale gelmişti. Önce klasik excel çözümlerini denedik, sonra sezgisel analiz (heuristic) yazalım dedik, o da olmayınca IP (integer programming) yolunu tuttuk. Ama bunların hiçbiri doğru cevabı veremedi. Verse bile bilgisayarın çalışma süresi beklentimizin çok üstünde çıkıyordu. Bildiğimiz bütün yolları tükettikten sonra o zamanlar Sabancı Üniversitesi'nde çalışan bölüm mezunlarımızdan Meltem Denizel hocama başvurdum. Bana Genetik Algoritmaları tavsiye etti. Biraz araştırma yaptıktan sonra denemeye karar verdim. İşte bu yazıda size hem biraz genetik algoritmaları tanıtmak (dilim döndüğünce ve anladığım kadarıyla), hem de üretimde nasıl bir uygulamaya gittiğimizi anlatmak istiyorum.

Alan Turing, 1950 yılında "learning machine" yani öğrenen makine terimini kullanıp, bilgisayarın kompleks problemlerin çözümünde evrim prensiplerini kullanmasını önermişti. 1957 yılında Alex Fraser genetik algoritmaların genel tanımını yapıp bu çalışma alanını netleştirdi ve ilk örnekleri verdi. O günden bu güne konuyla ilgili birçok araştırma yapıldı ve 90'lardan itibaren de piyasaya ticari çözümler sürülmeye başlandı. Genetik algoritmalar çözümü çok zor, belki mevcut tekniklerle imkansız problemlerde kullanılır. Özellikle yapay zeka geliştirme çalışmalarında çok önemli bir yer tutar. Neden böyle olduğunu bilmeyenler için algoritmaların çalışma mantığını açıkladıktan sonraya bırakıyorum.

Düşünün ki bir bilgisayara ya da bir insana adımın ne olduğunu sordum. Beş harften oluştuğunu da ekledim. Bunun dışında bana soru sorma hakkı yok, hakkımda hiçbir şey bilmiyor ve araştıramaz. Ama verdiği cevabın adıma ne kadar yaklaştığını bilme hakkı var. Onu da şöyle düşünelim; her doğru bildiği harf bir puan, doğru yerdeki doğru harf beş puan olsun. Örneğin, benim adım "Utkan" ve bana "Ahmet" diye cevap verdi. İki tane doğru harf var ama doğru yerlerde değiller, sonuç olarak iki puan aldı. Bilgisayarın tek bildiği bu kadar; verdiği cevabın kaç puan ettiği. Burada ancak iki yolu olabilir; birincisi 5 harfli bütün kombinasyonları denemek, ikincisi de genetik algoritmaları kullanmak. Sadece 5 harfli olduğu için bütün kombinasyonları denemesini bekleyebiliriz, ama daha kısa sürede çözebilecek bir yol varken neden buna zaman harcasın? Ya benim adım 250 harften oluşsaydı? Spekülasyonu bir kenara bırakıp genetik algoritma opsiyonuna dönebiliriz.

Bilgisayarımız kendisine beş haneden oluşacak bir dizi yapar. Bu dizi biyolojideki genlerin oluşturduğu kromozoma karşılık gelir. Bu diziye rassal 5 tane harf koyar. Sonra başka bir tane daha dizi yapar ve yine rassal seçtiği 5 tane harfi de bunun içine koyar. Bu şekilde, vereceğimiz bir üst sınıra kadar dizi yaratmaya devam eder. Aslında bir popülasyon oluşturmuştur. Sonra bunların arasında kötü olanları ayıklar. Bunun için yukarıdaki puanlama sistemini kullanarak, her bir diziyi puanlar ve en kötüleri eler. Elenen dizilerden kalan boşluğu doldurmak için iki yolu vardır; birincisi mutasyon, ikincisi üreme. Mutasyon, dizilerdeki bazı harflerin rassal olarak değişmesidir. Örneğin, popülasyonda "rtkyn" diye bir dizi olsun. Keyfen bunu seçip bir kopyasını alır ama ilk hanesini "u" yapar. Bu yeni dizimiz "utkyn" olur. Bir sonraki puanlamada bu dizi daha yüksek puan alacaktır. Üreme ise, iki dizinin farklı kısımlarının birleşip yeni bir dizi yapmasıdır. Örneğin, "utcom" dizisinden ilk 2 hane, "pykat" dizisinden son 3 hane gelsin, bebeğimiz "utkat" adında olur, çok sevilir, yüksek puan alır. Bu şekilde popülasyona yeni üyeler kazandırır. Puanlama sonrası kötüler elenir, tekrar üreme ve mutasyon opsiyonlarına döneriz. Peki, bu döngü ne zaman biter? Ne zaman iyi bir çözümle gelir?

Döngüyü bitirmenin birden fazla yolu vardır. En sevdiğimiz yol, tam doğru cevabın bulunmasıdır. "utkan" adında bir dizi ortaya çıkıp beklediğimiz 25 puanı alırsa algoritma durur ve kullanıcıya bu cevabı yansıtır. Ama dikkat ederseniz bütün sistem rassal bir yapıdadır. Haliyle, kısa bir sürede "utkan" cevabına ulaşamayabilir. Evet, teoride bulacaktır ama bunun için çok uzun çalışması gerekebilir. Diğer bir yol, belli bir zaman çalışması ya da döngü adedidir. Örneğin, bilgisayara bu algoritmayı 100 bin defa çalıştır diyebiliriz. Yüksek adette döngü yapılırsa, sonuçların iyi olmasını bekleriz, ama gereğinden fazla ya da az çalışmış olabilir, bunu bilemeyiz. Bunların üstüne en iyi yol, popülasyonun evrilmesidir. Zaman içinde kötüler elene elene, geriye yüksek puanlı diziler kalacaktır. Popülasyonun ortalamasını alıp, en yüksek skora sahibe oranlayınca farkın çok az olduğunu görürsek, evet popülasyon evrilmiş diyebiliriz. Bu noktada algoritma durur ve en yüksek puana sahip diziyi gösterir. Evet, yüzde yüz doğru cevap vermeyebilir, ama kabul edebileceğimiz bir noktaya gelmiş olabilir.

Algoritmanın detaylarında işleyişini önemli ölçüde etkileyecek unsurlar vardır. Örneğin, popülasyonda kaç üye olacağı, puanlama sonrası ne kadarının eleneceği, geriye kalanların ne oranda mutasyon ya da üremeye geçeceği ve belki de en önemlisi hangi şartlarda duracağını belirlemek gibi. Bunların yanlış seçimi, algoritmanın beklediğimiz performansı göstermesini engelleyebilir. Ayrıca, gen yapısının seçimi ya da bunu puanlayan sistemdeki hatalar da bizi doğru yoldan ayırabilir. Yukarıdaki örnekte doğru harf ve doğru yerdeki harfe verilen puanları eşit alsaydım, bana doğru cevap olarak "katun" diye bir şey de verebilirdi. Bu yüzden, kullanıcının sezgisel bir yol izleyip, modeli ve parametrelerini iyi kurması gerekir. Bu zorluk problemin non-lineer yapısından ya da matematikten uzak, daha çok algısal sonuçlarından kaynaklanabilir. Şöyle bir örnek verebiliriz; bilgisayarın güzel bir insan yüzü çizmesini istiyorsunuz. Bir yüzün çirkin ya da güzel olmasını bilgisayarın puanlamasını bekleyemeyiz, çünkü biz bunu onun anlayacağı matematiğe dökemeyiz. Göz, burun, dudak arası belli oranlar vardır, ama her detayı kodlayabilecek bilgiye sahip değiliz. Tek yapabileceğimiz, ürettiği çözümleri bize gösterip bizim vereceğimiz puana göre ilerlemesidir. Böylece, en azından bize güzel gelen bir şey yapmış olur. Richard Dawkins Kör Saatçi adlı kitabında bununla ilgili bir deneyini ve buna bağlayarak evrimin nasıl çalıştığını anlatır. Kitabın adı da buradan gelir. Okumanızı şiddetle tavsiye ederim. Özetle, genetik algoritmalar kompleks problemlerin çözümünde güçlü ama kırılgan bir yol sunar. Parametreler ve puanlama sistemi iyi seçilmezse hüsranla sonuçlanabilir. Ama üzerinde iyi düşünülmüş bir ekosistem yaratılırsa beklentilerin üstünde sonuçlar verebilir.

İşte bu motivasyonla, ben de şirketteki problemin üstüne eğildim. Sorun üretim hatlarında kolay ve zor ürünlerin istenen sırada gelmemesiydi. Ana üretim hattını besleyen yan hatlar bu dengesizlikten zorlanıyor, istenen verim alınamıyordu. Bunun için ürünleri 4 kategoriye almışlardı ve gün içinde bekledikleri ideal iş sıralaması şu şekildeydi;

1 - 2 - 3 - 4 - 3 - 2 - 1 - 2 - 3... Yani, 1'den 4'e artan, sonra azalan, sonra yine artan, testere şeklinde bir üretim sıralaması istiyorlardı. Fakat, o gün üretilmesi gerekenlerin sayısı bu şemaya uymayabiliyordu. Örneğin, elimizde çok fazla 2 ve 4 tipinde iş oluyordu. Aynı miktarda 3 tipi iş olmadığı için bekledikleri 2-3-4-3-2 sıralamasını yapamıyorduk. Eninde sonunda bir çözüm buluyorduk, ama bunun için çok uğraşılıyordu. Ben de bunun için genetik algoritmaları denemeye karar verdim. Üretimden bana bir puanlama tablosu yapmasını istedim. Örneğin 1'den sonra 4 gelirse şu kadar ceza puanı gibi, tek tek bütün kombinasyonları puanlattım. Sonra, uzun uğraşılarla kullanacağım gen dizisine karar verdim. Her bir dizi de ilk hane hangi tipten başlanacağını belirliyordu. Örneğin, 4 tipi. Sonra gelen hanelerin hepsinde 3 opsiyon vardı; artan, eşit veya azalan. Şöyle bir dizimiz olsun; 3 - artan - azalan - eşit - artan... Buna elimizdeki işleri verdiğimizde bize şöyle dönüyordu; 3-4-3-3-4. Elinde, diziye göre yeterli eleman yoksa, sıradaki diğer komutu deniyordu. Örneğin, 3'deyken sırada artan geldi ama elinde hiç 4 yok; o zaman artan yerine eşit tipine bakar, bulamazsa azalan tipine bakar, o da yoksa oyun biter zaten. Bunun gibi popülasyona binlerce üye attıracak, sonra puanlama-eleme-üreme/mutasyon-puanlama... şeklinde döngülerle kötüleri eleyip, en iyi çözümü bulacaktım.

Oturup kodu Visual Basic'de yazdım. Asıl zor kısım bundan sonraydı. Puanlama sonrası kaç dizinin eleneceği, mutasyon oranı (örneğin dizinin 5. hanesindeki artanı azalan yapması gibi), ne zaman duracağı gibi sorular beni çok uğraştırdı. Bunları deneye yanıla bulmam gerekiyordu. Ne yazık ki testleri yaptığım bilgisayarın kapasitesi düşüktü, benim de kodlama bilgim vasattı. Yine de yılmadım haftalarca uğraştım ve kabul edilebilir bir kombinasyona ulaştım. Sonra programı işi yapan arkadaşın bilgisayarına kurdum. Yaptığı tek şey excel'e siparişlerini girip bir tuşa basmasıydı. Genetik algoritma ekosistemi kurup yanlış hatırlamıyorsam 5 dakika içinde bulabildiği en iyi çözümle dönüyordu. Bazen küçük dokunuşlarla iyileştiriyorduk, ama çoğunlukla işi görüyordu. Projeyi Meltem Hocaya anlattım, "Beraber bir makale yazalım bundan." dedi. Önemli bir çalışma olacaktı, çünkü yerel sektörde bir örneğini görmemiştik. Bundan birkaç ay sonra şirketten ayrıldım. Yine de makaleyi yazmak istedik fakat şirketten onay alamadık, o yüzden burada da daha fazla bilgi veremiyorum.

Artık genetik algoritmaları kullanmak çok kolay. Hem yüksek işlem kapasiteli bilgisayarlara sahibiz, hem de benim uğraştığım gibi modeli sıfırdan kodlamanıza gerek yok. Bunu sizin için yapan ücretsiz modüller var. Örneğin, Excel'le gelen Solver içindeki algoritma, Excel'in formüllerini de kullanarak size güzel bir çözüm platformu yaratıyor. Daha gelişmiş versiyonları C# kodlarınıza ekleyerek de çalıştırabilirsiniz. Yeter ki modelinizin matematiksel iz düşümü net olsun, iyi çözüm şansı yüksek olacaktır. Dünya'da hayat başladığından bu yana evrim çalıştı ve bizi buraya kadar getirdi. Ayrıca, evrim bizden önce de var olan en kapsamlı ve tutarlı problem çözme tekniğidir. Bazı çözümlerini (kendimiz dahil) tam olarak anlayamıyoruz zaten. Bu yüzden, önümüzdeki en önemli problemleri ona çözdürmek akıllıca olacaktır. Yazının başında yapay zeka için kullanıldığından bahsetmiştim. Tam olarak anlamadığımız zekamızın yada bilincin bir örneğini yapmaya çalışıyoruz. Sezgisel bir yaklaşıma da sahip değiliz, haliyle geriye elimizde evrimin kadim yolu dışında bir şey kalmıyor. Umarım, bu sefer bizden iyisini yapar.

Sevgiler

<< Önceki Bölüm Sonraki Bölüm >>