Evolutionary algorithms are good general problem solver but suffer from a lack of domain specific knowledge. However, the problem specific knowledge can be added to evolutionary algorithms by hybridizing. Interestingly, all the elements of the evolutionary algorithms can be hybridized. In this chapter, the hybridization of the three elements of the evolutionary algorithms is discussed: the objective function, the survivor selection operator and the parameter settings. As an objective function, the existing heuristic function that construct the solution of the problem in traditional way is used. However, this function is embedded into the evolutionary algorithm that serves as a generator of new solutions. In addition, the objective function is improved by local search heuristics. The new neutral selection operator has been developed that is capable to deal with neutral solutions, i.e. solutions that have the different representation but expose the equal values of objective function. The aim of this operator is to directs the evolutionary search into a new undiscovered regions of the search space. To avoid of wrong setting of parameters that control the behavior of the evolutionary algorithm, the self-adaptation is used. Finally, such hybrid self-adaptive evolutionary algorithm is applied to the two real-world NP-hard problems: the graph 3-coloring and the optimization of markers in the clothing industry. Extensive experiments shown that these hybridization improves the results of the evolutionary algorithms a lot. Furthermore, the impact of the particular hybridizations is analyzed in details as well.