A novel metaheuristic for graph and graphset-T coloring problem

Çizgeyi boyama ve çizgeyi kümeli boyamaNP_zorkombinasyoneloptimizasyon problemleridir. Bu tezde, bu iki probleme çözüm getirmek için yapım ve yeniden yıkım prosedürü, kabul etme kriteri ve tepe tırmanma yönteminin bütünleştirildiği bir yöntem tasarlanmıştır. Yeni aday çözümler yapım ve yeniden yıkım prosedürü tarafından oluşturulurken, bu çözümler daha sonra tepe tırmanma yöntemi tarafından geliştirilmiştir. Geliştirilen çözüm belirli bir kabul etme kriterine göre kabul edilir ya da reddedilir. Buna ek olarak, iki farklı yöntem, kümeyi boyama problemi için tasarlanan yönteme ayrı ayrı eklenmiştir. İlk olarak, aynıçözümlerin yinelenmesini engellemek için tabu mekanizması algoritmaya entegre edilmiştir. Daha sonra ise belirli bir miktar çaprazlama işlemi gerçekleştirmek üzere algoritma popülasyon tabanlı yapıya dönüştürülmüştür. Amaç evrimsel algoritmada kullanılan çaprazlama işleminin sağladığıavantajlardan faydalanmaktır. Ayrıca çizgeyi kümeli boyama işlemi için de, mutasyon benzeri bir operatör sonuçları iyileştirmek için tasarlanan yapıya eklenmiştir. Tasarlanan yapı DIMACS ve GEOM test kümeleri üzerinde denenmiştir. Elde edilen sonuçlar bu iki alanda yapılan benzer ve en iyi sonuçları elde etmişçalışmalarla kıyaslanmıştır.