An improved genetic algorithm procedure is introduced in this work based on the theory of the most highly fit parents (both male and female) are most likely to produce healthiest offspring. It avoids the destruction of near optimal information and promotes further search around the potential region by encouraging the exchange of highly important information among the fittest solution. A novel crossover technique called Segmented Multi-chromosome Crossover is also introduced. It maintains the information contained in gene segments and allows offspring to inherit information from multiple parent chromosomes. The improved GA is applied for the automatic and simultaneous parameter optimization and feature selection of multi-layer perceptron network in medical disease diagnosis. Compared to the previous works, the average accuracy of the proposed algorithm is the best among all algorithms for diabetes and heart dataset, and the second best for cancer dataset.