Eliminating objective functions and warm starting algorithms using projections in multi-objective optimization

Abstract

Many real world optimization problems have more than a single objective. In order to solve these multi-objective problems exactly, usually one has to solve many single objective problems to obtain all the efficient solutions and nondominated points. As the size of the nondominated set increases, so does the computational effort required to solve multi-objective problems. One way to mitigate this and lessen the computational burden is to reduce the number of objective functions in a given problem. When there are redundant objective functions, this reduction is obvious and the only requirement then is to detect the redundant objectives. Otherwise, any reduction will result in information loss in the form of missing some nondominated points. In other words, the set of points that will be obtained from the reduced problem is going to be a representation, which is a subset of the nondominated set of the original problem. In this thesis, we develop a projection based metric in order to determine which objective to remove with the goal of keeping the information loss to a minimum. We base our approach on the characterization of a redundant objective for the linear case. We then assess the level of redundancy for an objective using its similarity to its projection. The performance of this method is evaluated on many sets of test problems from the literature as well as on generated correlated instances and the information loss is quantified using quality metrics. Our method demonstrates strong performance across the majority of tested problems. Moreover, we show that the representation we obtain after solving the reduced problem can be used to warm start the exact solution process of the original multi-objective problem. This way parts of the search region that do not contain any nondominated points can be eliminated and the number of objects that are needed to be maintained throughout the solution process can be reduced. Our preliminary experiments indicate that our initialization method is highly effective in achieving these reductions.

Gerçek hayatta karşılaşılan birçok eniyileme problemi birden fazla amaca sahiptir. Bu çok amaçlı problemleri tam çözmek ve tüm etkin çözümleri ve baskın noktaları elde etmek için genellikle birçok tek amaçlı problemin çözülmesi gerekir. Baskın kümenin boyutu arttıkça, çözüm için gereken hesaplama yükü de artacaktır. Bu hesaplama yükünü azaltmanın yollarından biri, amaç fonksiyonlarının sayısını eksiltmektir. Problemin gereksiz amaç fonksiyonları içerdiği durumda, bu eksiltmenin nasıl yapılacağı açıktır ve yapılması gereken gereksiz amaç fonsksiyonları tespit etmektir. Aksi takdirde, herhangi bir eksiltme, baskın nokta kümesinin tam olarak elde edilememesi şeklinde bir bilgi kaybına yol açar ve eksiltilmiş problemden elde edilecek baskın küme, asıl problemin baskın nokta kümesinin bir alt kümesi olan temsili çözümler olacaktır. Bu tezde, bilgi kaybını en aza indirebilme amacıyla hangi amaç fonksiyonunun eksiltileceğini belirlemek üzere yansıma tabanlı bir ölçüt geliştirilmiştir. Yaklaşım, doğrusal problemler için gereksiz amaç fonksiyonlarının özelliklerine dayanmaktadır. Bir amaç fonksiyonunun gereksizliği yansımasına benzerliği ölçülerek değerlendirilmiştir. Ölçütün performansı test problemleri ve çalışma kapsamında üretilen korelasyonlu problemler üzerinde sınanmış ve elde edilen temsili çözümler kalite ölçütleri kullanılarak değerlendirilmiştir. Yaklaşımımızın birçok problem türünde iyi performans gösterdiği görülmüştür. Ayrıca, eksiltilmiş problemi çözerek elde ettiğimiz temsili çözümlerin bazı özellikleri gösterilmiş ve bu çözümler asıl çok amaçlı problemin tam çözüm sürecini hızlı başlatmak için kullanılmıştır. Burada amaç baskın noktaların bulunmadığı bölgeleri çözüm sürecine dahil etmemek ve problemlerin tam çözüm süreçlerinde takip edilmesi gereken nesne sayısını azaltmaktır. Öncül deney sonuçları yaklaşımımızın gerekli nesne sayısını azaltmakta etkili olduğunu göstermiştir.