The rapid rise of malware challenges traditional detection methods due to code obfuscation and polymorphism. While machine learning classifiers offer quick detection and can identify complex malicious features, they are susceptible to backdoor attacks. We introduce GAT, a genetic algorithm-based approach for generating effective and stealthy Android backdoors. Using the SHAP interpretability tool, we first select efficient features as primary backdoors. A fitness function then enables iterative optimization through a genetic algorithm. Additionally, we propose a method to integrate backdoor features into the source code, maintaining functionality while facilitating attacks on Android classifiers in real data outsourcing scenarios. Our evaluation of the Drebin and Mamadroid malware detectors in data outsourcing scenarios indicates that an attack success rate exceeding 70% can be achieved with only 5% poisoned samples and a minimal number of trigger features, while keeping the false positive rate below 10% and the label flipping rate below 30%. Additionally, the performance degradation of the classifiers remains within 5%. This work provides new insights into backdoor attack methodologies in Android malware classifiers.