Advertisement
Published in:
2018 | OriginalPaper | Chapter
A Probabilistic Tree-Based Representation for Non-convex Minimum Cost Flow Problems
Authors : Behrooz Ghasemishabankareh, Melih Ozlen, Frank Neumann, Xiaodong Li
Published in: Parallel Problem Solving from Nature – PPSN XV
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.