Published January 1, 2016 | Version v1
Publication Open

Chemical Reaction Optimization for Max Flow Problem

Creators

  • 1. University of Jordan

Description

This study presents an algorithm for MaxFlow problem using "Chemical Reaction Optimization algorithm (CRO)".CRO is a recently established meta-heuristics algorithm for optimization, inspired by the nature of chemical reactions.The main concern is to find the best maximum flow value at which the flow can be shipped from the source node to the sink node in a flow network without violating any capacity constraints in which the flow of each edge remains within the upper bound value of the capacity.The proposed MaxFlow-CRO algorithm is presented, analyzed asymptotically and experimental test is conducted.Asymptotic runtime is derived theoretically.The algorithm is implemented using JAVA programming language.Results show a good performance with a complexity of O(I E2), for I iterations and E edges.The number of iterations I in the algorithm, is an important factor that will affect the results obtained.As number of iterations is increased, best possible max-Flow value is obtained.

⚠️ This is an automatic machine translation with an accuracy of 90-95%

Translated Description (Arabic)

تقدم هذه الدراسة خوارزمية لمشكلة MaxFlow باستخدام "خوارزمية تحسين التفاعل الكيميائي (CRO )". CRO هي خوارزمية ما وراء الاستدلال التي تم إنشاؤها مؤخرًا للتحسين، مستوحاة من طبيعة التفاعلات الكيميائية .الشاغل الرئيسي هو العثور على أفضل قيمة تدفق قصوى يمكن من خلالها شحن التدفق من عقدة المصدر إلى عقدة الحوض في شبكة التدفق دون انتهاك أي قيود على السعة يظل فيها تدفق كل حافة ضمن القيمة الحدية العليا للسعة .يتم تقديم خوارزمية MaxFlow - CRO المقترحة وتحليلها بشكل متقارب ويتم إجراء اختبار تجريبي .يتم اشتقاق وقت التشغيل المتقارب نظريًا .يتم تنفيذ الخوارزمية باستخدام لغة برمجة JAVA. تُظهر النتائج أداءً جيدًا مع تعقيد O(I E2)، للتكرارات والحواف E. عدد التكرارات I في الخوارزمية، هو عامل مهم سيؤثر على النتائج التي تم الحصول عليها. يتم زيادة عدد التكرارات، وأفضل قيمة ممكنة للتدفق الأقصى.

Translated Description (French)

Cette étude présente un algorithme pour le problème MaxFlow à l'aide de « Chemical Reaction Optimization algorithm (CRO) ».CRO est un algorithme méta-heuristique d'optimisation récemment établi, inspiré par la nature des réactions chimiques. La principale préoccupation est de trouver la meilleure valeur de flux maximale à laquelle le flux peut être expédié du nœud source au nœud récepteur dans un réseau de flux sans violer les contraintes de capacité dans lesquelles le flux de chaque bord reste dans la valeur limite supérieure de la capacité. L'algorithme MaxFlow-CRO proposé est présenté, analysé asymptotiquement et un test expérimental est effectué. Le temps d'exécution asymptotique est dérivé théoriquement. L'algorithme est mis en œuvre en utilisant le langage de programmation JAVA. Les résultats montrent une bonne performance avec une complexité de O(I E2), pour les itérations I et les bords E. Le nombre d'itérations I dans l'algorithme est un facteur important qui affectera les résultats obtenus. Au fur et à mesure que le nombre d'itérations augmente, la meilleure valeur max-Flow possible est obtenue.

Translated Description (Spanish)

Este estudio presenta un algoritmo para el problema MaxFlow utilizando "Chemical Reaction Optimization algorithm (CRO)" .CRO es un algoritmo meta-heurístico recientemente establecido para la optimización, inspirado en la naturaleza de las reacciones químicas. La principal preocupación es encontrar el mejor valor de flujo máximo al que se puede enviar el flujo desde el nodo de origen al nodo de destino en una red de flujo sin violar ninguna restricción de capacidad en la que el flujo de cada borde permanezca dentro del valor del límite superior de la capacidad. Se presenta el algoritmo MaxFlow-CRO propuesto, analizado asintóticamente y se realiza una prueba experimental. El tiempo de ejecución asintótico se deriva teóricamente. El algoritmo se implementa utilizando el lenguaje de programación JAVA. Los resultados muestran un buen rendimiento con una complejidad de O(I E2), para I iteraciones y E bordes. El número de iteraciones I en el algoritmo es un factor importante que afectará los resultados obtenidos. Se aumenta el número de iteraciones, se obtiene el mejor valor de flujo máximo posible.

Files

Paper_26-Chemical_Reaction_Optimization_for_Max_Flow_Problem.pdf.pdf

Files (984.9 kB)

⚠️ Please wait a few minutes before your translated files are ready ⚠️ Note: Some files might be protected thus translations might not work.
Name Size Download all
md5:0cf151d9f4d885229ed297711229a41b
984.9 kB
Preview Download

Additional details

Additional titles

Translated title (Arabic)
تحسين التفاعل الكيميائي لمشكلة التدفق الأقصى
Translated title (French)
Optimisation de la réaction chimique pour le problème de débit maximal
Translated title (Spanish)
Optimización de la reacción química para el problema de flujo máximo

Identifiers

Other
https://openalex.org/W2516202207
DOI
10.14569/ijacsa.2016.070826

Is supplement to
https://openalex.org/W4381463142 (Other)
https://openalex.org/W3141113327 (Other)
https://openalex.org/W2974330806 (Other)
https://openalex.org/W2069541586 (Other)
https://openalex.org/W1589346146 (Other)
https://openalex.org/W2339811963 (Other)
https://openalex.org/W184565551 (Other)
https://openalex.org/W2350803257 (Other)
https://openalex.org/W2028827726 (Other)
https://openalex.org/W3090447693 (Other)

GreSIS Basics Section

Is Global South Knowledge
Yes
Country
Jordan