A Proposed Genetic Algorithm Approach for the Kidney Exchange Problem

摘要

Approximately 10-15% of the population worldwide is affected by Chronic Kidney Diseases (CKD). The most severe form of CKD is an end-stage renal disease (ESRD) and the treatment for ESRD is either by dialysis or kidney transplantation. Around 30% of patients with ESRD have a willing living donor in time of transplant, but their donors are incompatible due to either blood group incompatibility or human leucocyte antigen sensitization of the recipient against the donor. Kidney Exchange Program (KEP) is a policy that aims to solve this issue by matching incompatible pairs of donors and recipients with other incompatible pairs, thus increasing the chance of both pairs of receiving a kidney. Most existing research applied the exact method to solve the KEP models, but this method has some drawbacks. This research aims to propose a Genetic Algorithms (GA) approach in order to maximize the potential number of transplants in KEP. The proposed method counts and extracts all the cycles and chains prior to starting the algorithm. This step will significantly decrease the computing time needed to run the algorithm, which is one of the drawbacks of using GA. The result showed that solving the KEP by GA approach has the potential of achieving optimal results with 88.8% matching efficiency.