League Championship Algorithm (LCA)

Saturday 2, November, 2013

The League Championship Algorithm (LCA) is a recently proposed algorithm for global optimization, which mimics the championship process in sport leagues. Beside the nature, culture, politics, human, etc as the typical sources of inspiration of various algorithms, the metaphor of sporting competitions is used for the first time in LCA. The methodology of LCA can be described as follows:

A number of individuals making role as sport teams compete in an artificial league for several weeks (iterations). Based on the league schedule in each week, teams play in pairs and their game outcome is determined in terms of win or loss (or tie), given known the playing strength (fitness value) along with the particular team formation/arrangement (solution) followed by each team. Keeping track of the previous week events, each team devises the required changes in its formation/playing style (a new solution is generated) for the next week contest and the championship goes on for a number of seasons (stopping condition). LCA is a population based algorithm where its “teams” are similar to PSO’s “particles” but with a quite different way of performing their search. The way in which a new solution associated to an LCA’s team is generated is governed via imitating the match analysis followed by coaches to design a suitable arrangement for their forthcoming match. In a typical match analysis, coaches will modify their arrangement on the basis of their own game experiences and their opponent’s style of play. The following keywords, which are commonly related to team games, are used metaphorically in LCA.

Sport league- A sports league is an organization that exists to provide a regulated competition for a number of people to compete in a specific sport. League is generally used to refer to competitions involving team sports, not individual sports. A league championship may be contested in a number of ways. Each team may play every other team a certain number of times in a round-robin tournament. In such a set-up, a team with the best record becomes champion, based on either a strict win-loss-tie system or on a points system where a certain number of points are awarded for a win, loss, or tie.

Formations- Normally each team has a playing style which can be realized during the game via team formation. A formation is a specific structure defining a distribution of players based on their positions within the field of play. For example, the most common formations in soccer are variations of 4-4-2, 4-3-3, 3-2-3-2, 5-3-2 and 4-5-1. Different formations can be used depending on whether a team wishes to play more attacking or defensive. Every team pursues a best formation which is often related to the type of players available to the coach.

Match analysis- match analysis refers to the objective recording and examination of behavioural events occurring during competitions. The main aim of match analysis when observing one’s own team’s performance is to identify strengths which can then be further built upon and weaknesses which suggest areas for improvement. Likewise, a coach analyzing opposition performance will use data to try to counter opposing strengths (threats) and exploit weaknesses (opportunities). An extremely important ingredient of the match analysis process is the presentation of feedback to players on their own or opponent’s performance through video footage, match reconstructions and presentation of data. Feedback can and should be given pre-match, post-match or in the build up to next match. Such kind of analysis is typically known as strengths/weaknesses/opportunities/threats (SWOT) analysis, which explicitly links internal (strengths and weaknesses) and external factors (opportunities and threats). Identification of SWOTs is essential because subsequent steps in the process of planning for achievement of the main objective may be derived from the SWOTs. The primary strength of SWOT analysis arises from matching specific internal and external factors and evaluating the multiple interrelationships involved. There are four basic categories of matches for which strategic alternatives can be considered:

  • S/T matches show the strengths in light of major threats from competitors. The team should use its strengths to avoid or defuse threats.
  • S/O matches show the strengths and opportunities. The team should attempt to use its strengths to exploit opportunities.
  • W/T matches show the weaknesses against existing threats. The team must attempt to minimize its weaknesses and avoid threats. Such strategies are generally defensive.
  • W/O matches illustrate the weaknesses coupled with major opportunities. The team should try to overcome its weaknesses by taking advantage of opportunities.

These strategies are used in the metaphorical “LCA match analysis process”, wherein each individual generates a new solution based on a SWOT like analysis.

Gap analysisThe SWOT analysis provides a structured approach to conduct the gap analysis. A gap is sometimes spoken of as “the space between where we are and where we want to be”. When the process of identifying gaps includes a deep analysis of the factors that have created the current state of the team, the groundwork has been laid for improvement planning. The gap analysis process can be used to ensure that the improvement process does not jump from identification of problem areas to proposed solutions without understanding the conditions that created the current state of the team.

Transfer-At the end of each season, teams review their performance over the past year and various changes may occur, e.g. changes in the coaching configuration, transfer of players or even changes in the managerial board. A transfer is the action taken whenever a player moves between clubs. It refers to the transferring of a player’s registration from one team to another.

LCA is a population based algorithmic framework for global optimization over a continuous search space. A common feature among all population based algorithms like LCA is that they attempt to move a population of possible solutions to promising areas of the search space during seeking the optimum. Similar to the most of population based algorithms a set of L solutions in the search space, chosen a priori at random, form the initial population of LCA. Using the sporting terminology, “league” in LCA stands for “population”. Like most of population based algorithms, LCA consists in evolving gradually the composition of the population in successive iterations, by maintaining the size of population constant. For the sake of consistency we may use “week” in place of “iteration”. Each solution in the population is associated to one of L teams (L is an even number) and is interpreted as the team’s current formation. Therefore, “team i” is matched to the “ith member of the population” and a particular “formation” for team i is matched to theth “solution” in the population. Each solution in the population has a certain fitness value, which measures its degree of adaptation to the objective aimed. In LCA the “fitness value” can be interpreted as the “playing strength” along with the intended team formation. Almost in all population-based algorithms a succession of operators is applied to individuals in each iteration to generate the new solutions for the next iteration. The way in which a new solution associated to an LCA’s team is generated is governed via imitating the match analysis process which is typically followed by coaches to design a suitable arrangement for their team. LCA make an analogy between the process of generating a new solution and the sport match analysis process. A broad group of population-based algorithms are Evolutionary Algorithms (EA) in which during iterations, the objective is to overall improve of the fitness of the individuals. Such a result is obtained by simulating the selection mechanism, which governs the evolution of the living beings through supporting the survival of the fittest individuals, according to the Darwinian Theory. As a pseudo evolutionary algorithm, selection in LCA is a greedy selection which replaces the current best formation with a more productive team formation having a better playing strength. The algorithm terminates after a certain number of “seasons” (S) being passed in which each season comprises L-1 weeks (iterations), yielding S*(L-1) weeks of contests.

Some characteristics of the regular championship environment are idealized to visualize the artificial championship modeled by LCA. Each of the following idealized rules will hsa an impact on different modules developed in LCA.

  • Idealized rule 1. It is more likely that a team with better playing strength wins the game. The term “playing strength” refers to ability of one team to beat another team.
  • Idealized rule 2. The outcome of a game is not foretellable given known the teams’ playing strength perfectly.
  • Idealized rule 3. The probability that team i beats team j is assumed equal from both teams point of view.
  • Idealized rule 4. The outcome of the game is only win or loss. Tie outcome is not considered in the basic version of LCA (We will later break this assumption via inclusion of the tie outcome, when introducing other variants of the algorithm).
  • Idealized rule 5. When team i beats team j, any strength helped team i to win has a dual weakness caused team j to lose. In other words, any weakness is a lack of a particular strength. An implicit implication of this rule is that while the match outcome is imputed to chance, teams do not believe it technically.
  • Idealized rule 6. Teams only focus on their upcoming match without regards of the other future matches. Formation settings are done just based on the previous week events.

The basic steps of the league championship algorithm can be represented as a schematic flowchart shown in the following Figure.

 

 

The main modules of LCA in the above flowchart are the manner of generating the league schedule, determining the winner/loser; and setting up a new formation for each team. To find more details on these modules and the whole mechanizm of LCA please see the following paper. More ideas can also be found in the publicatins list provided bellow.

 
To download an introductory paper on LCA  
 
     

To download the Powerpoint slides of LCA 

 
       

To download the Powerpoint slides of LCA (in Persian)

 
       

To download the Matlab source code of LCA for unconstrained optimization


 
       
To download Matlab demo software of LCA 
 
 

     Researches on League Championship Algorithm


  1. Jalili S, Husseinzadeh Kashan A, Hosseinzadeh  Y (2016). League championship algorithms for optimum design of pin-jointed structures. Journal of Computing in Civil Engineering, Accepted for Publication.

  2. Khoshalhan F, Nedaie  A (2016). A New Play-off Approach in League Championship Algorithm for Solving Large-Scale Support Vector Machine Problems. International Journal of Industrial Engineering & Production Research, 27, 1, 61-68.

  3. Abdulhamid SM, Abd Latiff MS, Abdul-Salaam G, Hussain Madni SH (2016). Secure Scientific Applications Scheduling Technique for Cloud Computing Environment Using Global League Championship Algorithm. PLoS ONE 11(7): e0158102. doi:10.1371/journal.pone.0158102.
  4. Moghadasi M (2015). Design of Image Processing methods using League Championship Algorithm and Optics Inspired OptimizationMs.C Thesis, Azad University, Science and Research branch, Iran (in Persian).

  5. علي اصغر حيدري، علی عباسپور (1393). یک روش تلفیقی بر مبنای هندسه محاسباتی و الگوریتم LCA جهت مسیر یابی سکوهای نامحسوس در محیط های دینامیک. اولین کنفرانس ملی ریاضیات صنعتی 

  6. Xu w, Wang R, Yang J (2015). An improved league championship algorithm with free search and its application on production scheduling, Journal of Intelligent Manufacturing. 

  7. Xu1a W, Yang J, Wang R (2015). An Intelligent Method for Evaluation of Production Scheduling Performance. International Conference on Intelligent Systems Research and Mechatronics Engineering (ISRME 2015), 1121-1126.

  8. Seyedhosseini SM, Badkoobehi H, Noktehdan A (2015). Machine-Part Cell Formation Problem Using a Group Based League Championship Algorithm. Journal of Promotion Management, 21, 55-63.

  9. Abdulhamid SM, Abd Latiff MS, Abdullahi M (2015). Job Scheduling Technique for Infrastructure as a Service Cloud Using an Improved League Championship Algorithm. The Second International Conference on Advanced Data and Information Engineering (DaEng-2015). 

  10. Abdulhamid SM, Abd Latiff MS, Hussain Madni SH, Oluwafemi O (2015). A Survey of League Championship Algorithm: Prospects and Challenges. Indian Journal of Science and Technology, 8, 101-110, DOI: 10.17485/ijst/2015/v8iS3/60476.

  11. Badrloo S (2015). A new method for solving combinatorial optimization problems with permutation based solution structure using league championship algorithm. Ms.C Thesis, Azad University, Science and Research branch, Iran (in Persian).

  12. Eyvazi M (2015). Portfolio optimization problem with multi-period investment readjustment using league championship algorithmMs.C Thesis, Tarbiat Modares University, Iran (in Persian).

  13. Xu w, Yang J, Tan H, Jin L, Wang R (2014). Improved league championship algorithm and its application in production scheduling. Applied Science and Technology. 10.3969/j.issn.1009-671X.201408012.

  14. Abdulhamid SM, Abd Latiff MS, Ismaila I (2014). Tasks scheduling technique using league championship algorithm for makespan minimization in IAAS cloud. ARPN Journal of Engineering and Applied Sciences, 9(12), 2528-2533.

  15. Abdulhamid SM, Abd Latiff MS (2014). League Championship Algorithm Based Job Scheduling Scheme for Infrastructure as a Service Cloud. 5th International Graduate Conference on Engineering, Science and Humanities (IGCESH2014), Universiti Teknologi Malaysia, Johor Bahru, Malaysia.   

  16. Sajadi SM, Husseinzadeh Kashan A, Kahledan S (2014). A New approach for permutation flow-Shop scheduling problem using league championship algorithm. Joint International Symposium on CIE44 and IMSS’14.

  17. Bouchekara HREH, Abido MA, Chaib AE, Mehasni R (2014). Optimal power flow using the league championship algorithm: A case study of the Algerian power system. Energy Conversion and Management, 87, 58-70.

  18. Bouchekara H, Dupré L, Kherrab H, Mehasni R (2014). DESIGN OPTIMIZATION OF ELECTROMAGNETIC DEVICES USING THE LEAGUE CHAMPIONSHIP ALGORITHM. Optimization & Inverse problems in Electromagnetism, OIPE 2014.

  19. Sebastián AR, Isabel LR (2014). Scheduling To Job Shop Configuration Minimizing The Makespan Using Champions League Algorithm. The 1st International Conference on Systems Engineering Research - 2014 CIIIS, Colombia, 120-129.

  20. سیاوش خالدان، سید مجتبی سجادی، علی حسین زاده کاشانارائه یک راه حل مبتنی بر الگوریتم قهرمانی در لیگهای ورزشی برای حل مساله فروشنده دوره گرد. دومین کنفرانس ملی مهندسی صنایع و سیستمها، دانشگاه آزاد اسلامی واحد نجف آباد، اسفند 1392.

  21. سیاوش خالدان، سید مجتبی سجادی، علی حسین زاده کاشان. ارائه یک راه حل برای مساله فروشنده دوره گرد با استفاده از الگوریتم قهرمانی در لیگهای ورزشی و مقایسه عملکرد آن با راه حل مبتنی بر الگوریتم ژنتیک اصلاح شده. اولین همایش ملی مدیریت کسب و کار، همدان، بهمن 1392.

  22. Husseinzadeh Kashan A (2014). League Championship Algorithm (LCA): A new algorithm for global optimization inspired by sport championships. Applied Soft Computing, 16, 171-200.

  23. Kahledan S (2014). A League Championship Algorithm for Travelling Salesman ProblemMs.C Thesis, Azad University, Najaf Abad branch, Iran (in Persian).

  24. Edraki S (2014). A new approach for engineering design optimization of centrifuge pumps based on league championship algorithmMs.C Thesis, Azad University, Science and Research branch, Iran (in Persian).

  25. Sun J, Wang X, Li K, Wu C, Huang M, Wang X (2013). An Auction and League Championship Algorithm Based Resource Allocation Mechanism for Distributed Cloud. Advanced Parallel Processing Technologies, Lecture Notes in Computer Science, 8299, 334-346.

  26. Lenin K, Ravindranath Reddy B, Surya Kalavathi M (2013). League Championship Algorithm (LCA) for Solving Optimal Reactive Power Dispatch Problem. International Journal of Computer & Information Technologies, Vol 1, Issue 3.

  27. James Stephen M, Prasad Reddy P.V.G.D (2013). Simple League Championship AlgorithmInternational Journal of Computer Applications, 75, 28-32.

  28. Tavasoli Kejani H (2013). A new approach for reliability optimization based on league championship algorithm (LCA). Ms.C Thesis, Azad University, Najaf Abad branch, Iran (in Persian).

  29. Husseinzadeh Kashan A, Karimiyan S, Karimiyan M, Husseinzadeh Kashan H (2012). A modified League Championship Algorithm for numerical function optimization via artificial modeling of the “between two halves analysis”. The 6th International Conference on Soft Computing and Intelligent Systems and The 13th International Symposium on Advanced Intelligent Systems, 1944-1949.

  30. Pourali Z, Aminnayeri M (2012). A novel discrete league championship algorithm for minimizing earliness/tardiness penalties with distinct due dates and batch delivery consideration. Lecture Notes in Computer Science, 6838, 139-146

  31. Husseinzadeh Kashan A (2011). An Efficient Algorithm for Constrained Global Optimization and Application to Mechanical Engineering Design: League Championship Algorithm (LCA). Computer-Aided Design, 43, 1769-1792.

  32. Husseinzadeh Kashan A, Karimi B (2010). A new algorithm for constrained optimization inspired by the sport league championships. WCCI 2010 IEEE World Congress on Computational Intelligence, 487-494.

  33. Husseinzadeh Kashan A (2009). League Championship Algorithm: a new algorithm for numerical function optimization. SoCPaR 2009 IEEE International Conference of Soft Computing and Pattern Recognition, 43-48.