Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
A Probabilistic Tree-Based Representation for Non-convex Minimum Cost Flow Problems
verfasst von : Behrooz Ghasemishabankareh, Melih Ozlen, Frank Neumann, Xiaodong Li
Erschienen in: Parallel Problem Solving from Nature – PPSN XV
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Network flow optimisation has many real-world applications. The minimum cost flow problem (MCFP) is one of the most common network flow problems. Mathematical programming methods often assume the linearity and convexity of the underlying cost function, which is not realistic in many real-world situations. Solving large-sized MCFPs with nonlinear non-convex cost functions poses a much harder problem. In this paper, we propose a new representation scheme for solving non-convex MCFPs using genetic algorithms (GAs). The most common representation scheme for solving the MCFP in the literature using a GA is priority-based encoding, but it has some serious limitations including restricting the search space to a small part of the feasible set. We introduce a probabilistic tree-based representation scheme (PTbR) that is far superior compared to the priority-based encoding. Our extensive experimental investigations show the advantage of our encoding compared to previous methods for a variety of cost functions.