Maximum cut in fuzzy nature: Models and algorithms

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:234

Article

Wang, Rui-Sheng^1,2  Wang, Li-Min³ 

[1] Osaka Sangyo Univ, Dept Elect Informat & Commun Engn, Osaka 5748530, Japan

[2] Renmin Univ China, Dept Math, Beijing 100872, Peoples R China

[3] China Univ Min & Technol, Beijing 100083, Peoples R China

关键词: Max-Cut;    Fuzzy coefficients;    Mathematical models;    Fuzzy simulation;    Genetic algorithm;   

DOI  :  10.1016/j.cam.2009.12.022

来源: Elsevier

【 摘 要 】

The maximum cut (Max-Cut) problem has extensive applications in various real-world fields, such as network design and statistical physics. In this paper, a more practical version, the Max-Cut problem with fuzzy coefficients, is discussed. Specifically, based on credibility theory, the Max-Cut problem with fuzzy coefficients is formulated as an expected value model, a chance-constrained programming model and a dependent-chance programming model respectively according to different decision criteria. When these fuzzy coefficients are represented by special fuzzy variables like triangular fuzzy numbers and trapezoidal fuzzy numbers, the crisp equivalents of the fuzzy Max-Cut problem can be obtained. Finally, a genetic algorithm combined with fuzzy simulation techniques is designed for the general fuzzy Max-Cut problem under these models and numerical experiment confirms the effectiveness of the designed genetic algorithm. (C) 2009 Elsevier B.V. All rights reserved.

【 授权许可】

Free